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)$?

  • 4
    $\begingroup$ By Kannan's theorem, for all positive integers $k$, $\Sigma^P_4$ is not in $\mathrm{size}(n^k)$. $\endgroup$ – Sasho Nikolov Nov 16 '14 at 22:16
  • 1
    $\begingroup$ Ah and this extends to $\Sigma_2$, right? Then basically the next hardest thing is already NP. $\endgroup$ – Jeremy Kun Nov 16 '14 at 22:39
  • 3
    $\begingroup$ I 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$. $\endgroup$ – Sasho Nikolov Nov 16 '14 at 23:06
  • 4
    $\begingroup$ It’s true for oblivious $S^P_2$. $\endgroup$ – Emil Jeřábek supports Monica Nov 16 '14 at 23:10
  • $\begingroup$ Okay so EXP is trivial then. I guess it was a stupid question after all :) I just forgot about Kannan's theorem. $\endgroup$ – Jeremy Kun Nov 17 '14 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.