Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I am not sure in the sense of: If I were dropped on a desert island, I could derive a water-tight proof of this result from scratch.

I am confident, though, based upon my reading of secondary sources written by people that I trust.

From one of Bengio's works (http://www.iro.umontreal.ca/~bengioy/papers/ftml.pdf): "More interestingly, there are functions computable with a polynomial-size logic gates circuit of depth k that require exponential size when restricted to depth k − 1 (Hastad, 1986)."



I think my argument was mistaken. The CNF form I was thinking of involves adding unknown variables so it doesn't actually allow you to compute the function in one step.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: