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-...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
reference-request × 969algorithms × 208
complexity-theory × 110
graphs × 81
optimization × 57
terminology × 50
formal-languages × 47
data-structures × 42
machine-learning × 38
programming-languages × 37
np-complete × 33
books × 29
automata × 27
logic × 27
time-complexity × 25
education × 25
history × 25
computational-geometry × 24
type-theory × 24
computability × 23
finite-automata × 21
parallel-computing × 21
approximation × 20
artificial-intelligence × 19
computation-models × 19