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-...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible