<p>Is it known that <span class="math-container">$\mathsf{E} \subset \mathsf{NP} \subset \mathsf{SIZE}[n^k]$</span> is false?</p>
<p>It is easy to show that the relaxed version (<span class="math-container">$\mathsf{E} \subset \mathsf{NP}$</span> and <span class="math-container">$\mathsf{P}^{\mathsf{NP}} \subset \mathsf{SIZE}[n^k]$</span>) is false, as <span class="math-container">$\mathsf{P}^{\mathsf{E}} = \mathsf{EXP}$</span>, which has no fixed polynomial size circuits. I cannot prove the above question though.</p>

CC BY-SA 4.0
2024-08-30T06:29:19.820Z
Sure, this is false. $\mathrm{E\subseteq NP}$ implies $\mathrm{EXP=NP=coNP}$ by a padding argument, and as you say, there are languages in EXP that require circuit size $\Omega(n^{k+1})$. (In fact, there are such languages in the polynomial hierarchy. Direct diagonalization gives such a language in $\Sigma^P_4$ or so. The best currently known bound, a recent result of Li, following up on Chen, Hirahara and Ren, is that there is such a language in $\mathrm{S^P_2}$.)
Emil Jeřábek
CC BY-SA 4.0
2024-08-30T08:13:03.760Z
(I meant $\mathrm{O^P_2}$. The $\mathrm{S^P_2}$ result has been known for much longer.)
Emil Jeřábek
CC BY-SA 4.0
2024-08-30T17:24:29.503Z
@EmilJeřábek Thanks! Don't know how I missed the normal padding argument
Stefan G.
<cc.complexity-theory><complexity-classes><circuit-complexity>
Is it known that $\mathsf{E} \subset \mathsf{NP} \subset \mathsf{SIZE}[n^k]$ is false?
Stefan G.
# Is it known that $\mathsf{E} \subset \mathsf{NP} \subset \mathsf{SIZE}[n^k]$ is false?

(Asked by: username_0 on 2024-08-30)

Is it known that $\mathsf{E} \subset \mathsf{NP} \subset \mathsf{SIZE}[n^k]$ is false?

It is easy to show that the relaxed version ($\mathsf{E} \subset \mathsf{NP}$ and $\mathsf{P}^{\mathsf{NP}} \subset \mathsf{SIZE}[n^k]$) is false, as $\mathsf{P}^{\mathsf{E}} = \mathsf{EXP}$, which has no fixed polynomial size circuits. I cannot prove the above question though.

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity

> **Comments:**
> **username_1**: Sure, this is false. $\mathrm{E\subseteq NP}$ implies $\mathrm{EXP=NP=coNP}$ by a padding argument, and as you say, there are languages in EXP that require circuit size $\Omega(n^{k+1})$. (In fact, there are such languages in the polynomial hierarchy. Direct diagonalization gives such a language in $\Sigma^P_4$ or so. The best currently known bound, a recent result of Li, following up on Chen, Hirahara and Ren, is that there is such a language in $\mathrm{S^P_2}$.)  
> **username_1**: (I meant $\mathrm{O^P_2}$. The $\mathrm{S^P_2}$ result has been known for much longer.)  
> **username_0**: @EmilJeřábek Thanks! Don't know how I missed the normal padding argument  

---

## 0 answers

