Introduction

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?

Climb the Levels

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

<p class="hint">Climb the hierarchy. Each level adds one quantifier block to a fixed Boolean formula over the variables <b>a b c</b>. <b>&exist;</b> means “there exists a value”, <b>&forall;</b> means “for all values”. <b>Solve</b> answers the current question by brute force and shows how many formula evaluations it took.</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">Press Solve to answer this question.</div>
<div class="meter" id="meter"></div>
<div class="btns">
  <button id="climb" type="button">Climb a level &uarr;</button>
  <button id="solve" type="button">Solve</button>
  <button id="reset" type="button" class="ghost">Reset to &Sigma;&#8321;</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// The polynomial hierarchy by hand. We fix a Boolean formula F over a,b,c and
// ask quantified questions like  exists a . forall b . exists c . F.
// Sigma_k = k alternating blocks STARTING with "exists". Climbing adds one block.
// Answering means evaluating F at every leaf of the quantifier tree: each new
// block multiplies the number of evaluations by 2 (one variable per block here),
// which is exactly why one extra alternation makes the search blow up.
var VARS = ['a','b','c'];
// F(a,b,c) = (a OR b) AND (NOT b OR c) AND (a OR NOT c)
function F(a,b,c){ return (a||b) && (!b||c) && (a|| !c); }
var evalF = function(env){ return F(env.a, env.b, env.c); };

var level = 1;            // current Sigma level (1..3)
var evals = 0;            // formula evaluations in the last Solve

// Quantifier for block i (0-based): even -> exists, odd -> forall (Sigma starts at exists).
function quantOf(i){ return (i % 2 === 0) ? 'E' : 'A'; }

// Recursively evaluate the quantified formula over the first `level` variables.
// Variables beyond `level` are existentially closed so F is fully determined
// (keeps the toy self-contained; the alternation structure is what matters).
function evaluate(idx, env){
  if (idx === level){
    // remaining vars (if any) existentially closed
    return closeRest(level, env);
  }
  var q = quantOf(idx), v = VARS[idx];
  var t = Object.assign({}, env); t[v] = true;  var rt = evaluate(idx+1, t);
  var f = Object.assign({}, env); f[v] = false; var rf = evaluate(idx+1, f);
  return (q === 'E') ? (rt || rf) : (rt && rf);
}
// Existentially close any variables past the quantified prefix.
function closeRest(start, env){
  if (start === VARS.length){ evals++; return evalF(env); }
  var v = VARS[start];
  var t = Object.assign({}, env); t[v] = true;
  var f = Object.assign({}, env); f[v] = false;
  return closeRest(start+1, t) || closeRest(start+1, f);
}

function quantString(){
  var s = '';
  for (var i=0;i<level;i++){ s += (quantOf(i)==='E'?'∃':'∀') + ' ' + VARS[i] + ' . '; }
  return s + 'F(a,b,c)';
}
function render(){
  document.getElementById('quant').textContent = quantString();
  document.getElementById('climb').disabled = (level >= VARS.length);
}
function setStatus(t,cls){ var s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
function drawMeter(n){
  var m=document.getElementById('meter'); m.innerHTML='';
  var cap=Math.min(n,64);
  for(var i=0;i<cap;i++){ var d=document.createElement('div'); d.className='tick'; m.appendChild(d); }
}

function solve(){
  evals = 0;
  var ans = evaluate(0, {});
  drawMeter(evals);
  var label = (level===1?'Σ₁ (= NP)': level===2?'Σ₂':'Σ₃');
  setStatus(fmt('%v% — %label% answered in %evals% formula evaluations.', { v: ans?'TRUE':'FALSE', label: label, evals: evals }),
            ans?'ok':'bad');
  console.log('level', level, 'answer', ans, 'evals', evals);
}
function climb(){ if(level<VARS.length){ level++; render(); setStatus('Added one alternation — now press Solve.',''); document.getElementById('meter').innerHTML=''; } }
function reset(){ level=1; render(); setStatus('Press Solve to answer this question.',''); document.getElementById('meter').innerHTML=''; }

document.getElementById('climb').addEventListener('click', climb);
document.getElementById('solve').addEventListener('click', solve);
document.getElementById('reset').addEventListener('click', reset);
render();
Result
Console

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 Real Complexity

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.
  • Σ1=NP\Sigma_1 = \text{NP} (one "exists" block), Π1=co-NP\Pi_1 = \text{co-NP} (one "for all" block).
  • Σk\Sigma_k = questions of the form exists … for all … exists … with k alternating blocks; Πk\Pi_k is the same starting with for all. The whole union over all k is PH.
  • Each floor sits inside the next: Σk⊆Σk+1\Sigma_k \subseteq \Sigma_{k+1} and Σk⊆Πk+1\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 Σk=Σk+1\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.
  • PH⊆PSPACE\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.

Where It Matters

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 Σ2\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 ≤s\le s that for all inputs matches this function?" is a classic Σ2\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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/polynomial-hierarchy/Content licensed under CC BY-NC 4.0.