Exercise

Propagate a Collapse of the Polynomial Hierarchy

Show that equality of adjacent PH levels collapses every higher level.

Problem

Let $\Sigma_0^p=\Pi_0^p=P$ and $\Sigma_{k+1}^p=NP^{\Sigma_k^p}$ , $\Pi_k^p=co\Sigma_k^p$ . Prove that if $\Sigma_k^p=\Pi_k^p$ for some $k\ge1$ , then $\mathrm{PH}=\Sigma_k^p$ . Make the induction step explicit rather than merely saying that quantifiers merge.

Prerequisites

Know the unit definitions and how resources are measured against encoded input length. Distinguish a conditional theorem, a reduction, and an algorithm.

Hint 1

Use the alternating-quantifier characterization with a polynomial-time predicate.

Hint 2

Replace the inner $\Pi_k^p$ predicate by an equivalent $\Sigma_k^p$ predicate.

Hint 3

Adjacent existential blocks combine into one polynomially bounded block.

Full solution

It suffices first to show $\Sigma_{k+1}^p\subseteq\Sigma_k^p$ . Let $L\in\Sigma_{k+1}^p$ . In quantifier form,

x\in L\iff \exists y_1\ \forall y_2\cdots Q_{k+1}y_{k+1}\ R(x,y_1,\ldots,y_{k+1}),

where all strings have polynomial length and $R$ is polynomial-time. For fixed $(x,y_1)$ , the remaining predicate begins universally and lies in $\Pi_k^p$ . By the hypothesis $\Pi_k^p=\Sigma_k^p$ , it has an equivalent $k$ -block description beginning existentially:

\exists z_1\ \forall z_2\cdots Q_k z_k\ R'(x,y_1,z_1,\ldots,z_k).

Substituting this description places the outer $\exists y_1$ next to $\exists z_1$ . Pair the two polynomial-length strings into one string. The result has only $k$ alternating blocks and begins existentially, so $L\in\Sigma_k^p$ . The reverse inclusion follows from monotonicity of PH levels; hence $\Sigma_{k+1}^p=\Sigma_k^p$ .

Taking complements and using the hypothesis gives

\Pi_{k+1}^p=co\Sigma_{k+1}^p=co\Sigma_k^p=\Pi_k^p=\Sigma_k^p.

Now induct on $j\ge k$ . Suppose $\Sigma_j^p=\Pi_j^p=\Sigma_k^p$ . Applying the same one-level argument at level $j$ yields $\Sigma_{j+1}^p=\Sigma_j^p$ , and complementing yields the corresponding $\Pi$ equality. Therefore every level at or above $k$ equals $\Sigma_k^p$ ; lower levels are contained in it. Since

\mathrm{PH}=\bigcup_{j\ge0}\Sigma_j^p,

we conclude $\mathrm{PH}=\Sigma_k^p$ .

The equality assumption is stronger than the ordinary containment $\Sigma_k^p\subseteq\Sigma_{k+1}^p$ . It allows changing the polarity of the inner $k$ -level predicate so the first two quantifier blocks have the same type and can merge. Polynomial bounds are preserved because pairing two polynomial-length witnesses still yields polynomial length.

For $k=1$ , the hypothesis is $NP=coNP$ , and the proof gives $\mathrm{PH}=NP$ . This is conditional; no such equality is currently known.

Checkpoints

Check both logical directions, halting of every relevant branch, and that output length and construction time are polynomial in the encoded input length.

Common mistakes

Merging unlike quantifier blocks before using the collapse hypothesis.
Proving only level $k+1$ collapses and omitting induction.
Presenting the conditional equality as a known theorem about the real world.

Σ₀ᴾ = Π₀ᴾ = Ppolynomial-time predicate

Begins existentiallyBegins universally

Sources and verification

Arora-Barak draft, sec. 5.2
Papadimitriou, ch. 17
Corpus coverage note: No direct merged-summary or 2026 transcript coverage.
Catalog mapping: data/exercises.json; statements and solutions are independently written; personal submissions are non-authoritative.

Provenance and confidence

The exercise is an original synthesis. Confidence reflects verification of the mathematical claim against the textbook sources listed above; course sources are used only where direct coverage is identified.

Open in the visualization gallery: Polynomial hierarchy lattice