Polynomial Hierarchy

The problem 'does there exist a circuit with a minimum number of gates equivalent to a given one?' is not merely NP-hard - it is harder than any problem in NP. Such problems live on the second floor of an infinite tower of classes above NP. The Polynomial Hierarchy is that tower, and understanding its structure means understanding how much different 'degrees of nondeterminism' differ from one another.

• **Model checking and verification:** properties of the form 'for all error scenarios there exists a recovery' are natural Π₂ problems that cannot be reduced to NP without exponential blowup.
• **Cryptographic security games:** security of an encryption scheme is formulated as 'for all adversaries A there exists a simulator S...' - quantifier alternation over agent roles directly corresponds to PH levels.
• **AI planning with partial observability:** classical planning is in PSPACE, but with k alternations of observability/hiddenness it falls in the Σₖ level of PH.

The Σ and Π levels of the Polynomial Hierarchy

NP can be characterized through existence: L ∈ NP if and only if there exists a polynomially verifiable certificate. co-NP is the negation: L ∈ co-NP if and only if a certificate of non-membership is polynomially verifiable. The Polynomial Hierarchy (PH) extends this pattern by alternating ∃ and ∀ quantifiers.

Example of a Σ₂ problem: 'Does there exist a formula φ such that no formula of smaller size is equivalent to it?' - requires checking existence of φ (∃) and for all φ' of smaller size non-equivalence (∀). Example from Π₂: 'For all k-colorings of graph G, at least one edge is monochromatic' - here ∀ comes first.

Oracle Machines

A Turing machine with **oracle** O is a TM with an extra query tape: it writes a string w onto the query tape, enters a 'query' state, and in the next step receives a yes/no answer to the question 'w ∈ O?' - in one step, regardless of the complexity of O. The class NP^A denotes problems solvable in nondeterministic polynomial time with an oracle to language A.

**Alternation theorem** (Chandra-Kozen-Stockmeyer): PH = APTIME = ATM with poly-time and O(1) alternations. This gives a combinatorial intuition: each level of the hierarchy is a game with a fixed number of moves between two players (∃ and ∀).

An important corollary: if SAT ∈ P (i.e., P = NP), then PH collapses to P. If NP = co-NP, then Σ₁ = Π₁, and PH collapses to Σ₁ = NP. Each such collapse would be a sensational result.

Relativization and Its Limits

In 1975 Baker, Gill and Solovay proved the relativization theorem: there exist oracles A and B such that P^A = NP^A and P^B ≠ NP^B. This means: **any proof of P vs NP that 'relativizes' (holds for every oracle) cannot resolve the question**, since the answer differs for different oracles.

**What 'relativizes' means:** a proof of P = NP relativizes if for every oracle O it proves P^O = NP^O. Diagonalization (time-space tradeoffs, Space Hierarchy Theorem, etc.) relativizes. Algebraic methods (IP = PSPACE - Shamir 1992) do not relativize.

From the relativization theorem it follows that proving P ≠ NP requires **non-relativizing** techniques - methods that use the internal structure of computations, not merely their inputs and outputs. Algebrization (Aaronson-Wigderson, 2009) showed that even algebraic generalizations are insufficient: fundamentally new methods are needed.

Collapse Theorems

A key property of PH: any 'unexpected' coincidence of levels implies collapse of the entire hierarchy. This makes PH structurally fragile: if anything collapses - everything collapses. The most important implications:

Quantified Boolean Formulas (QBF, TQBF) - the PSPACE-complete problem: '∃x₁ ∀x₂ ∃x₃ ... φ(x₁,...,xₙ) = 1?' with unbounded quantifier alternation. It sits above PH: if PH = PSPACE, then TQBF ∈ PH, which most researchers consider unlikely.

**Practical relevance of PH:** Σ₂ problems arise in verification (model checking with quantifiers), AI planning (partial observability creates levels of uncertainty), cryptography (security games with alternating roles of attacker and defender). Knowing a problem's level in PH gives a lower bound on its complexity.

Key Ideas

• **PH is built by quantifiers:** Σₖ = ∃∀∃... (k quantifiers), Πₖ = ∀∃∀... (k quantifiers); Σ₁ = NP, Π₁ = co-NP, PH = union of all levels.
• **Oracle machine = level of hierarchy:** Σₖ = NP with an oracle to Σₖ₋₁; each level gives the machine access to the previous level in a single step.
• **BGS theorem forbids diagonalization:** there exist oracles A, B with P^A = NP^A and P^B ≠ NP^B, so diagonalizing techniques cannot in principle resolve P vs NP.
• **Collapse is fragile:** NP = co-NP pulls PH → Σ₁ = NP; Σₖ = Πₖ for any k pulls PH → Σₖ. The hierarchy 'breaks in cascade'.

Related Topics

The Polynomial Hierarchy connects several fundamental concepts in complexity theory:

• Interactive Proofs (IP) — IP = PSPACE; a non-relativizing proof that bypasses the BGS barrier through algebrization
• Space Hierarchy — PH ⊆ PSPACE; the Space Hierarchy Theorem proves infinity of the space hierarchy by diagonalization (which is impossible for PH)

Вопросы для размышления

• If P = NP were proven, the entire polynomial hierarchy would collapse to P. What does this say about the nature of 'complexity levels' - are they real or an artifact of our ignorance?
• The BGS theorem shows that for different oracles the answer to P vs NP differs. Does this mean the P vs NP question itself depends on the 'computational context', or is it evidence of the limitations of diagonalization?
• Each level of PH adds one quantifier. What is the computational meaning of 'one quantifier' - what exactly does the transition from Σₖ to Σₖ₊₁ give in terms of computational power?

Связанные уроки

• alg-01-big-o