Back to Boolean Circuits
Back to notes

# Collapse Theorems

80%

• If $\NP\subseteq\Ppoly$, then $\PH=\P^{\NP}=\Sigma^{\P}_2=\Pi^{\P}_2$.

It suffices to show that if $\NP\in\Ppoly$, then $\Pi^{\P}_2\subseteq\Sigma^{\P}_2$. Recall that for any $L\in\Pi^{\P}_2$ and $n\in\N$, there exists a polynomial-size boolean formula $\phi_n$ such that for any $x\in\bit^n$, $x\in L$ iff $\forall y\exists z \phi_n(x,y,z)=1$.\

Let $\phi_{x}(y,z)=\phi_n(x,y,z)$ such that $x\in L$ iff $\forall y\exists z \phi_x(y,z)=1$ iff $\exists C_x\forall y C_x(y)=1$, where the last equation is due to the assumption $\NP\subseteq\Ppoly$ and $|C_x|=\poly(|x|)$ and thus $L\in\Sigma^{\P}_2$.

• If $\PSPACE\subseteq\Ppoly$, then $\PSPACE=\MA$.

Let $L\in\PSPACE$, by the assumption, there exists $\poly(n)$ size circuit $C_n$ such that $x\in L$ iff $C_n(x)=1$ for all $x\in\bit^n$. Now the goal is to design an $\MA$ protocol for $L$. Recall that $\PSPACE=\IP$ and by the assumption that $\PSPACE\subseteq\Ppoly$, there exists a polynomial size circuit family ${C_n}$ that simulates the response of the prover.

As a result, one can simulate the $\IP$ protocol for $L$ in one round as follows. First, Merlin sends all the circuits correponding to the length that have been queried by the verifier. Note that there are at most polynomial many of them and there are all of polynomial size, thus, Merlin only sends polynomially many bits to Arthur. Next, Arther simply simulates both the verifier the prover using the circuits sent by Merlin.

One can immediately see that the completeness holds. The soundness also hols since once Merlin sends the circuits, he already committed to a prover strategy and thus the soundness of this $\MA$ protocol follows from the soundness of the $\IP$ protocol.

• If $\EXP\subseteq\Ppoly$, then $\EXP=\MA$.

As $\PSPACE\subseteq\EXP$, the assumption implies $\PSPACE=\MA$. Thus, it suffices to show that $\EXP\subseteq\PSPACE$. For any $L\in\EXP$. The key observation here is that if $\EXP\subseteq\Ppoly$, then there exists a family of polynomial size circuits that computes the transition table of the exponential time Turing machines that computes $L$. As a result, one can simply non-deterministically guess the polynomial size circuit for transition table and verify all the steps. Note that all the operations can be done in polynomial space and $\PSPACE=\NPSPACE$.

• If $\NEXP\subseteq\Ppoly$, then $\NEXP=\MA$.
• If $\EXP^{\NP}\subseteq\Ppoly$, then $\EXP^{\NP}=\MA$.
• If $\NP\subseteq\Ppoly$, then $\NP\subseteq\ZPP^{\NP}$.

If $\NP\subseteq\Ppoly$, then $\PH=\MA$.