What is the best known lower bound against (nonuniform) circuits of size $O(n)$? I understand that we don't know of any explicit functions that need circuits of size more than something like $5n$. But are there existential results saying, e.g., that $\text{EXP} \not \subset \text{SIZE}(n)$?
Asked
Active
Viewed 139 times
3
-
4By Kannan's theorem, for all positive integers $k$, $\Sigma^P_4$ is not in $\mathrm{size}(n^k)$. – Sasho Nikolov Nov 16 '14 at 22:16
-
1Ah and this extends to $\Sigma_2$, right? Then basically the next hardest thing is already NP. – Jeremy Kun Nov 16 '14 at 22:39
-
3I am sorry, you are right, Kannan's theorem is for $\Sigma_2^P$, the proof uses the result for $\Sigma_4^P$, which is easy to prove, and the Karp-Lipton theorem. I think it's even true for $\Sigma_2^P \cap \Pi_2^P$. – Sasho Nikolov Nov 16 '14 at 23:06
-
4It’s true for oblivious $S^P_2$. – Emil Jeřábek Nov 16 '14 at 23:10
-
Okay so EXP is trivial then. I guess it was a stupid question after all :) I just forgot about Kannan's theorem. – Jeremy Kun Nov 17 '14 at 01:00