The Polynomial Hierarchy

NP is the class of questions of the form "does there exist a short proof?" — does there exist a route, a coloring, a satisfying assignment. Flip it and you get co-NP: "is it true for all cases?" — is every assignment unsatisfying, is there no route at all.

But the most interesting questions mix the two. "Is there a move I can make such that, for all of my opponent's replies, I still win?" "What is the smallest circuit such that for every input it computes the right answer?" Each "there exists … for all …" is a new layer of nesting.

Stack those alternating quantifiers and you build the polynomial hierarchy (PH): NP and co-NP on the first floor, then a second floor, a third, and — as far as anyone has proven — floors going up forever. This article is about that tower and the haunting question at its center: does it ever stop?

Below is a ladder. Each rung adds one more quantifier alternation to a Boolean question. Level $\Sigma_1$ asks "does there exist an x that makes the formula true?" — that is plain NP. Level $\Sigma_2$ asks "does there exist an x such that for all y …?". Level $\Sigma_3$ adds another "there exists z …", and so on.

<p class="hint">{{hint}}</p>
<div class="quant" id="quant">&exist; a . F(a,b,c)</div>
<div class="formula">F = (a OR b) AND (NOT b OR c) AND (a OR NOT c)</div>
<div class="status" id="status">{{status_init}}</div>
<div class="meter" id="meter"></div>
<div class="btns">
  <button id="climb" type="button">{{btn_climb}}</button>
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.quant { font: 700 22px ui-monospace, monospace; color: #1d3557; background: #e8eef3;
         border: 1px solid #cdd9e3; border-radius: 10px; padding: .7rem .9rem; margin: .3rem 0;
         overflow-x: auto; white-space: nowrap; }
.formula { font: 600 14px ui-monospace, monospace; color: #555; margin: 0 0 .6rem; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.meter { display: flex; gap: 3px; flex-wrap: wrap; margin: .3rem 0 .7rem; }
.meter .tick { width: 9px; height: 18px; background: #1d3557; border-radius: 2px; opacity: .85; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }

// Code not found

Press Climb a level to add an alternation, then Solve to let the computer answer the current question by brute force. Watch the counter: each new quantifier block multiplies the work, because the machine must check every value of the new variables nested inside everything before it. One extra alternation can turn a quick search into an exhausting one — and that growth is exactly what the hierarchy measures.

The hierarchy was defined in 1972 by Albert Meyer and Larry Stockmeyer. Here is the structure, level by level.

• Floor 0 is P — solvable outright, no guessing.
• $\Sigma_1 = \text{NP}$ (one "exists" block), $\Pi_1 = \text{co-NP}$ (one "for all" block).
• $\Sigma_k$ = questions of the form exists … for all … exists … with k alternating blocks; $\Pi_k$ is the same starting with for all. The whole union over all k is PH.
• Each floor sits inside the next: $\Sigma_k \subseteq \Sigma_{k+1}$ and $\Sigma_k \subseteq \Pi_{k+1}$. Nobody has proven any of these containments is strict.

Now the open questions, and they are deep:

• Does PH collapse? If for some k we had $\Sigma_k = \Sigma_{k+1}$, the whole tower would flatten to that one level. It is widely believed the hierarchy is infinite (every floor strictly above the last), but this is unproven.
• It's tied to P vs NP. If P = NP, the entire hierarchy collapses to P — a single floor. So proving PH is infinite would immediately prove P ≠ NP.
• $\text{PH} \subseteq \text{PSPACE}$, and whether that containment is strict is also open. A true quantified Boolean formula with unbounded alternations is PSPACE-complete — the hierarchy is the "bounded-alternation" piece of that.

So the polynomial hierarchy is not a solved staircase. It is a tower we can describe perfectly but cannot prove has more than one floor — a precise restatement of why P vs NP is so hard.

Whenever a problem has the shape "is there a choice such that no matter what happens, something holds?", it lives somewhere on this ladder:

• Games and adversaries: "is there a winning first move against every reply?" is a $\Sigma_2$ question; adding more turns climbs higher. This is why two-player games are a natural home for the hierarchy.
• Optimal / minimal design: "is there a circuit of size $\le s$ that for all inputs matches this function?" is a classic $\Sigma_2$ problem — optimization with a built-in "for all" check.
• Planning under uncertainty: "is there a plan that succeeds for every adversarial environment?" alternates your choices with the world's.
• Classifying hardness precisely: the hierarchy lets theorists say exactly how hard a problem is — not just "hard," but "two alternations hard," which is sharper than lumping everything under NP. It directly extends SAT into quantified SAT (QBF).

Even if PH never collapses, knowing which floor a problem sits on tells you how much alternating search any algorithm must, in the worst case, perform.

The polynomial hierarchy starts with a single word — exists — and grows by alternation. Add for all, then exists again, and you climb floor by floor into questions that look genuinely harder than plain NP. We can define every level precisely; the demo lets you feel the work multiply with each rung.

And yet the central fact remains stubbornly open: we believe the tower is infinite, but no one has proven it has even a second distinct floor. A collapse anywhere would ripple all the way down — and a collapse to the ground floor would mean P vs NP is resolved. The polynomial hierarchy is, in the end, the same great mystery wearing infinitely many faces.