3
votes
Shannon's result that some Boolean functions require exponential circuits
The best known lower bounds for explicit functions are $\Omega(n)$. The only superpolynomial lower bounds are in restricted models of circuits, such as monotone circuits and bounded-depth circuits.
NP-...
- 269k
Only top scored, non community-wiki answers of a minimum length are eligible