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

CC BY-SA 3.0
2014-11-16T22:16:54.670Z
By Kannan's theorem, for all positive integers $k$, $\Sigma^P_4$ is not in $\mathrm{size}(n^k)$.
Sasho Nikolov
CC BY-SA 3.0
2014-11-16T22:39:48.210Z
Ah and this extends to $\Sigma_2$, right? Then basically the next hardest thing is already NP.
Jeremy Kun
CC BY-SA 3.0
2014-11-16T23:06:24.790Z
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$.
Sasho Nikolov
CC BY-SA 3.0
2014-11-16T23:10:30.367Z
It’s true for oblivious $S^P_2$.
Emil Jeřábek
CC BY-SA 3.0
2014-11-17T01:00:09.617Z
Okay so EXP is trivial then. I guess it was a stupid question after all :) I just forgot about Kannan's theorem.
Jeremy Kun
<circuit-complexity><lower-bounds><advice-and-nonuniformity>
What is the strongest known lower bound against SIZE(n)?
Jeremy Kun
# What is the strongest known lower bound against SIZE(n)?

(Asked by: username_0 on 2014-11-16)

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

**Tags:** circuit-complexity, lower-bounds, advice-and-nonuniformity

> **Comments:**
> **username_1**: By Kannan's theorem, for all positive integers $k$, $\Sigma^P_4$ is not in $\mathrm{size}(n^k)$.  
> **username_0**: Ah and this extends to $\Sigma_2$, right? Then basically the next hardest thing is already NP.  
> **username_1**: 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$.  
> **username_2**: It’s true for oblivious $S^P_2$.  
> **username_0**: Okay so EXP is trivial then. I guess it was a stupid question after all :) I just forgot about Kannan's theorem.  

---

## 0 answers

