<p>We know if <span class="math-container">$NP\subseteq P/poly$</span> then <span class="math-container">$PH=\Sigma_2$</span> Then We want to show that <span class="math-container">$\Sigma_2-SAT\in P/poly$</span>. Now <span class="math-container">$$\phi\in \Sigma_2-SAT\iff \exists\ x\in\{0,1\}^{p_1(n)}\ \forall\ y\in \{0,1\}^{p_2(n)},\ \phi(x,y)=1$$</span>
Now consider the language <span class="math-container">$L=\{(\phi,x)\mid \forall \ y\in\{0,1\}^{p_2(n)},\ \phi(x,y)=1\}$</span>. This language is a <span class="math-container">$coNP$</span> problem. Since <span class="math-container">$P/poly$</span> is closed under complementation <span class="math-container">$L\in P/poly$</span>. Hence there exists a polynomial-size circuit of <span class="math-container">$(\phi,x)$</span>.</p>
<p>But at this point i am stuck how to get a polynomial size circuit of <span class="math-container">$\phi$</span> from <span class="math-container">$(\phi,x)$</span></p>

CC BY-SA 4.0
2023-04-21T13:07:27.517Z
Plug it into the expression for $\Sigma_2$-SAT. You will obtain that $\Sigma_2$-SAT is in NP/poly. Now use the assumption once more.
Emil Jeřábek
CC BY-SA 4.0
2023-04-21T13:08:59.877Z
Anyway, this is not a research-level question, and as such it is off-topic on this site. It would be appropriate for https://cs.stackexchange.com .
Emil Jeřábek
<sat><np><polynomial-hierarchy><circuits>
$NP\subseteq P/poly\implies PH\subseteq P/poly$
Sassy Math
# $NP\subseteq P/poly\implies PH\subseteq P/poly$

(Asked by: username_0 on 2023-04-21)

We know if $NP\subseteq P/poly$ then $PH=\Sigma\_2$ Then We want to show that $\Sigma\_2-SAT\in P/poly$. Now $$\phi\in \Sigma\_2-SAT\iff \exists\ x\in\{0,1\}^{p\_1(n)}\ \forall\ y\in \{0,1\}^{p\_2(n)},\ \phi(x,y)=1$$
Now consider the language $L=\{(\phi,x)\mid \forall \ y\in\{0,1\}^{p\_2(n)},\ \phi(x,y)=1\}$. This language is a $coNP$ problem. Since $P/poly$ is closed under complementation $L\in P/poly$. Hence there exists a polynomial-size circuit of $(\phi,x)$.

But at this point i am stuck how to get a polynomial size circuit of $\phi$ from $(\phi,x)$

**Tags:** sat, np, polynomial-hierarchy, circuits
> **Comments:**
> **username_1**: Plug it into the expression for $\Sigma_2$-SAT. You will obtain that $\Sigma_2$-SAT is in NP/poly. Now use the assumption once more.  
> **username_1**: Anyway, this is not a research-level question, and as such it is off-topic on this site. It would be appropriate for https://cs.stackexchange.com .  

---

## 0 answers

