Computational Complexity

Monday, June 20, 2005

 
Favorite Theorems: The Polynomial-Time Hierarchy

Posted by Lance

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:

• Σ₁^p=NP
• Σ_k+1^p=NP^Σ_kp, where NP^A 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 Σ_k^p 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, Σ_k^p=Σ_k+1^p then for all j≥k, Σ_k^p=Σ_j^p. 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.

6:48 PM #

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

   7:40 PM, June 20, 2005

2.  Anonymous says:  
   
   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
   

   6:38 PM, June 27, 2005

3.  Anonymous says:  
   
   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.)
   

   9:43 PM, June 27, 2005