Monday, June 20, 2005

Favorite Theorems: The Polynomial-Time Hierarchy

May Edition

The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space by Albert Meyer and Larry Stockmeyer, FOCS (then called SWAT) 1972.

The title result of this paper gave an early example of a natural problem that provably does not have an efficient algorithm. But it is the second half of the paper that developed one of the most important concepts in computational complexity.

The class NP consists of those problems with efficiently verifiable solutions. Similar to the arithmetic hierarchy, Meyer and Stockmeyer define a hierarchy above NP inductively as follows:

  • Σ1p=NP
  • Σk+1p=NPΣkp, where NPA represents the class of problems solvable in nondeterministic polynomial time with access to an oracle for solving problems in A.
The union of all of the Σkp form the polynomial-time hierarchy. The Meyer-Stockmeyer paper and follow-up papers by Stockmeyer and Celia Wrathall showed many interesting properties about the hierarchy including:
  • Alternation characterizations of the hierarchy using quantifiers and second-order logic.
  • If for any k, Σkpk+1p then for all j≥k, Σkpjp. If this happens for some k we say the polynomial-time hierarchy collapses, otherwise the we say the hierarchy is infinite.
  • PSPACE contains the polynomial-time hierarchy and if the converse holds then the hierarchy collapses.
The polynomial-time hierarchy has had a major impact in computational complexity in many area, including
  • classifying some problems like succinct set cover and VC dimension that NP does not capture,
  • using the conjecture that the hierarchy is infinite to imply the likelihood of a number of statements like that NP does not have small circuits and that graph isomorphism is not NP-complete,
  • attempts to show the polynomial-time hierarchy is infinite in relativized worlds have led to major results on circuit lower bounds,
  • led to the concept of alternation giving new characterizations of time and space-bounded classes, and
  • variations on the hierarchy led to interactive proof systems that themselves led to probabilistically checkable proofs and hardness of approximation results.
Much more in my recent paper on Larry Stockmeyer.


  1. Lance,
    I think you recently told that this problem is not "natural":)

  2. I seem to recall that the SIGACT News complexity theory column was going to run a column on problems complete for "high" levels of the polynomial hierarchy. (Here "high" means >2). Did that ever happen?

    -David Molnar

  3. Marcus Schaefer and Chris Umans wrote a two-part survey on completeness in the polynomial-time hierarchy for SIGACT News. (Most of the problems are in the second level, but some are in the third.)

  4. As practical (i.e. non-theoretic) programmer that needed to learn about PSPACE-to-NFA_universality algorithm, this paper was very bizzare

    "okay, so this paper actually explaines EXPSPACE-to-SqNFA_uni, but I can deal with that
    waaait, why is there still half a paper left? it's... polynomial heirarchy? did authors steal it to add to the end, lol?"

    having learned about PH only from wikipedia... I did not know this paper was a classic of this scale

    (also PSPACE-to-NFA_uni construction derived from this paper and appearing in several textbooks can be shortened and optimized at least in half...)