IP ⊆ AM collapses the polynomial hierarchy

Unconditional · against free reductions · Sha90, BM88

Statement

If IP is contained in AM, then $\mathbf{PSPACE}\subseteq {\mathbf{\Pi }}_2^{\mathbf{P}}$ and the polynomial hierarchy collapses to its second level, since $\mathbf{IP}=\mathbf{PSPACE}$ — Sha90 — and $\mathbf{AM}\subseteq {\mathbf{\Pi }}_2^{\mathbf{P}}$ — BM88.

Sketch

${\mathbf{\Sigma }}_2^{\mathbf{P}}\cup {\mathbf{\Pi }}_2^{\mathbf{P}}\subseteq \mathbf{PH}\subseteq \mathbf{PSPACE}=\mathbf{IP}\subseteq \mathbf{AM}\subseteq {\mathbf{\Pi }}_2^{\mathbf{P}}$, so ${\mathbf{\Sigma }}_2^{\mathbf{P}}={\mathbf{\Pi }}_2^{\mathbf{P}}=\mathbf{PH}=\mathbf{PSPACE}$.

Notes

• Constant-round interactive proofs are contained in AM: $\mathbf{IP}[k]\subseteq \mathbf{AM}[k+2]$ — GS86 — and $\mathbf{AM}[k]=\mathbf{AM}$ for constant $k$ — BM88. The collapse concerns IP with polynomially many rounds.