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:
- Σ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.
- Alternation characterizations of the hierarchy using quantifiers and second-order logic.
- If for any k, Σkp=Σk+1p then for all j≥k, Σkp=Σjp. 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.
- 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.
I think you recently told that this problem is not "natural":)
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?ReplyDelete
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.)ReplyDelete