8.4 The polynomial hierarchy

The polynomial hierarchy extends beyond NP and co-NP, offering a more nuanced view of problem complexity. It's like a ladder, with each rung representing a new level of difficulty. As you climb, problems get tougher, involving more back-and-forth between different types of questions.

This hierarchy helps us understand the space between easy problems (in P) and the hardest ones (in PSPACE). It's a key tool for sorting out which problems are trickier than others, even when they're all pretty challenging. The structure gives us clues about how different complexity classes relate to each other.

The Polynomial Hierarchy

Definition and Structure

Top images from around the web for Definition and Structure

• 

  File:Map-of-complexity-science.jpg - Wikipedia View original

  Is this image relevant?

• 

  Complexity class - Wikipedia View original

  Is this image relevant?

• 

  Category:Computational complexity theory - Wikimedia Commons View original

  Is this image relevant?

• 

  File:Map-of-complexity-science.jpg - Wikipedia View original

  Is this image relevant?

• 

  Complexity class - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Definition and Structure

• 

  File:Map-of-complexity-science.jpg - Wikipedia View original

  Is this image relevant?

• 

  Complexity class - Wikipedia View original

  Is this image relevant?

• 

  Category:Computational complexity theory - Wikimedia Commons View original

  Is this image relevant?

• 

  File:Map-of-complexity-science.jpg - Wikipedia View original

  Is this image relevant?

• 

  Complexity class - Wikipedia View original

  Is this image relevant?

1 of 3

• Polynomial hierarchy classifies complexity classes extending beyond NP and co-NP providing a finer-grained structure for problems of increasing complexity
• Consists of an infinite sequence of classes denoted as $[PH](https://www.fiveableKeyTerm:ph) = \bigcup_{k} \Sigma_{k}^p$, where k represents the level of the hierarchy
• Σ (Sigma) classes represent languages decidable by existential quantifiers with $\Sigma_{0}^p = P$ and $\Sigma_{1}^p = NP$
• Π (Pi) classes represent languages decidable by universal quantifiers with $\Pi_{0}^p = P$ and $\Pi_{1}^p = co-NP$
• Δ (Delta) classes defined as $\Delta_{k}^p = P^{\Sigma_{k-1}^p}$ represent languages decidable by deterministic polynomial-time Turing machines with oracle access to the previous level
• Each level k of the hierarchy defined recursively with $\Sigma_{k}^p = NP^{\Sigma_{k-1}^p}$ and $\Pi_{k}^p = co-NP^{\Sigma_{k-1}^p}$
• Hierarchy collapses if there exists a k such that $\Sigma_{k}^p = \Sigma_{k+1}^p$ implying all higher levels are equal to $\Sigma_{k}^p$
  • Collapse leads to significant simplification of the complexity landscape
  • Impacts our understanding of the relationships between different complexity classes

Quantifier Alternation and Oracle Machines

• Levels of the hierarchy characterized by alternating quantifiers
  • Each level adds one more quantifier alternation (existential or universal)
  • Example: $\Sigma_2^p$ problems have form $\exists x \forall y \phi(x, y)$ where φ is a polynomial-time predicate
• Oracle machines play crucial role in defining hierarchy levels
  • Oracle provides answers to decision problems from lower levels
  • Allows simulation of more complex computations within polynomial time
• Quantifier structure relates to real-world scenarios
  • Game-theoretic problems (chess positions with limited moves)
  • Verification processes with multiple stages of checking

Relationships Within the Hierarchy

Class Inclusions and Complements

• Classes at each level k related as follows: $\Sigma_{k}^p \subseteq \Delta_{k+1}^p \subseteq \Sigma_{k+1}^p$ and $\Pi_{k}^p \subseteq \Delta_{k+1}^p \subseteq \Pi_{k+1}^p$
• Complement of a language in $\Sigma_{k}^p$ belongs to $\Pi_{k}^p$ and vice versa for all k ≥ 0
• Each level contains union of Σ and Π classes from previous level: $\Sigma_{k}^p \cup \Pi_{k}^p \subseteq \Delta_{k+1}^p$
• Hierarchy considered proper if all inclusions are strict meaning $\Sigma_{k}^p \subsetneq \Sigma_{k+1}^p$ and $\Pi_{k}^p \subsetneq \Pi_{k+1}^p$ for all k ≥ 0
• If P = NP entire polynomial hierarchy collapses to P as all classes would be equal
• Relationship between adjacent levels expressed using alternating quantifiers with each level adding one more quantifier alternation
  • Example: $\Sigma_3^p$ problems have form $\exists x \forall y \exists z \phi(x, y, z)$

Collapse and Separation

• Collapse of hierarchy occurs if any two adjacent levels are equal
  • Implies all higher levels also collapse to that level
• Separation of levels crucial open question in complexity theory
  • Proof of strict separation would resolve P vs NP problem
• Relativization barrier shows limitations of certain proof techniques
  • Oracle results demonstrate both collapse and separation possible relative to different oracles
• Connection to other complexity classes
  • PH contained within PSPACE
  • If PH = PSPACE significant implications for complexity theory landscape

Problems in the Hierarchy

Lower Levels (NP and co-NP)

• $\Sigma_1^p$ (NP) problems include
  • SAT (Boolean satisfiability)
    • Determine if a given Boolean formula has a satisfying assignment
  • Hamiltonian Path
    • Find a path in a graph visiting each vertex exactly once
• $\Pi_1^p$ (co-NP) problems include
  • TAUTOLOGY (determining if a Boolean formula is always true)
  • UNSAT (unsatisfiability)
    • Determine if a Boolean formula has no satisfying assignments

Higher Levels and Complete Problems

• $\Sigma_2^p$ problems include
  • QSAT₂ (quantified Boolean formula with one existential and one universal quantifier)
    • Example: $\exists x_1, \ldots, x_n \forall y_1, \ldots, y_m \phi(x_1, \ldots, x_n, y_1, \ldots, y_m)$
  • Minimal DNF (finding smallest disjunctive normal form of a Boolean formula)
• $\Pi_2^p$ problems include
  • QSAT₂' (complement of QSAT₂)
  • ALLMINSAT (determining if all minimal satisfying assignments of a Boolean formula have a specific property)
• Higher levels contain increasingly complex problems often involving multiple alternations of quantifiers or nested optimization problems
  • Example: Graph coloring with alternating player moves
  • Succinct circuit representations of large graphs
• Complete problems for each level serve as representatives for hardest problems within that class
  • Reduction techniques used to prove completeness
  • Examples: Generalized versions of chess or Go with limited moves

Implications for NP and Beyond

Structural Insights

• Polynomial hierarchy provides framework for classifying problems believed harder than NP-complete problems but still within PSPACE
• If NP ≠ co-NP then polynomial hierarchy does not collapse to its first level suggesting rich structure of complexity classes beyond NP
• Existence of complete problems for each level implies if any level collapses all higher levels collapse to that level
• Polynomial hierarchy contained within PSPACE and if PH = PSPACE significant implications for structure of complexity classes
  • Would suggest limited power of additional quantifiers beyond certain point

Applications and Techniques

• Study of polynomial hierarchy led to important techniques in complexity theory
  • Use of oracle machines and relativization
  • Development of interactive proof systems
• Understanding structure of polynomial hierarchy crucial for developing more refined approximation algorithms and parameterized complexity results for hard problems
  • Example: Approximation algorithms for $\Sigma_2^p$-complete problems
  • Parameterized complexity for problems at higher levels of PH
• Polynomial hierarchy provides natural way to classify quantified Boolean formulas and certain game-theoretic problems based on number of alternations in player moves or quantifiers
  • Applications in artificial intelligence and game theory
  • Modeling complex decision-making processes with multiple stakeholders