All Questions
1 question
7
votes
1
answer
413
views
Implications of the $\Omega(\frac{2^n}{n})$ circuit lower bound being tight
There is a basic result in circuit complexity that says:
There exists a language that cannot be solved with circuits of size $o(\frac{2^n}{n})$.
The argument is a simple counting argument on the ...
- 579