- Polynomial hierarchy
In
computational complexity theory , the polynomial hierarchy is a hierarchy ofcomplexity class es that generalize the classes P, NP andco-NP tooracle machine s.Definitions
There are multiple equivalent definitions of the classes of the polynomial hierarchy.
- For the oracle definition of the polynomial hierarchy, define
:Delta_0^{ m P} := Sigma_0^{ m P} := Pi_0^{ m P} := mbox{P},
where P is the set of
decision problem s solvable inpolynomial time . Then for i ≥ 0 define:Delta_{i+1}^{ m P} := mbox{P}^{Sigma_i^{ m P:Sigma_{i+1}^{ m P} := mbox{NP}^{Sigma_i^{ m P:Pi_{i+1}^{ m P} := mbox{coNP}^{Sigma_i^{ m P
where AB is the set of
decision problem s solvable by aTuring machine in class A augmented by an oracle for some complete problem in class B. For example, Sigma_1^{ m P} = { m NP}, Pi_1^{ m P} = { m coNP} , and Delta_2^{ m P} = { m P^{NP is the class of problems solvable in polynomial time with an oracle for some NP-complete problem. - For the existential/universal definition of the polynomial hierarchy, let L be a language (i.e. a
decision problem , a subset of {0,1}*), let p be apolynomial , and define: exists^p L := left{ x in {0,1}^* left| left( exists w in {0,1}^{leq p(|x|)} ight) langle x,w angle in L ight. ight},
where langle x,w angle in {0,1}^* is some standard encoding of the pair of binary strings "x" and "w" as a single binary string. "L" represents a set of ordered (red) pairs of strings, where the first string "x" is a member of exists^p L, and the second string "w" is a "short" (w| leq p(|x|) ) witness testifying that "x" is a member of exists^p L. In other words, x in exists^p L if and only if there exists a short witness "w" such that langle x,w angle in L . Similarly, define
: forall^p L := left{ x in {0,1}^* left| left( forall w in {0,1}^{leq p(|x|)} ight) langle x,w angle in L ight. ight} Note that deMorgan's Laws hold: left( exists^p L ight)^{ m c} = forall^p L^{ m c} and left( forall^p L ight)^{ m c} = exists^p L^{ m c} , where "L"c is the complement of "L".
Let mathcal{C} be a class of languages. Extend these operators to work on whole classes of languages by the definition
:exists^{ m P} mathcal{C} := left{exists^p L | p mbox{ is a polynomial and } L in mathcal{C} ight}:forall^{ m P} mathcal{C} := left{forall^p L | p mbox{ is a polynomial and } L in mathcal{C} ight}
Again, deMorgan's Laws hold: m co} exists^{ m P} mathcal{C} = forall^{ m P} { m co} mathcal{C} and m co} forall^{ m P} mathcal{C} = exists^{ m P} { m co} mathcal{C} , where m co}mathcal{C} = left{ L^c | L in mathcal{C} ight}.
The classes NP and
co-NP can be defined as m NP} = exists^{ m P} { m P} , and m coNP} = forall^{ m P} { m P} , where P is the class of all feasibly (polynomial-time) decidable languages. The polynomial hierarchy can be define recursively as:Sigma_0^{ m P} := Pi_0^{ m P} := { m P} :Sigma_{k+1}^{ m P} := exists^{ m P} Pi_k^{ m P} :Pi_{k+1}^{ m P} := forall^{ m P} Sigma_k^{ m P}
Note that m NP} = Sigma_1^{ m P} , and m coNP} = Pi_1^{ m P} .
This definition reflects the close connection between the polynomial hierarchy and the
arithmetical hierarchy , where R and RE play roles analogous to P and NP, respectively. Theanalytic hierarchy is also defined in a similar way to give a hierarchy of subsets of the real numbers. - An equivalent definition in terms of
alternating Turing machine s defines Sigma_k^{ m P} (respectively, Pi_k^{ m P}) as the set of decision problems solvable in polynomial time on an alternating Turing machine with k alternations starting in an existential (respectively, universal) state.
Relations between classes in the polynomial hierarchy
The definitions imply the relations:
:Sigma_i^{ m P} subseteq Delta_{i+1}^{ m P} subseteq Sigma_{i+1}^{ m P}:Pi_i^{ m P} subseteq Delta_{i+1}^{ m P} subseteq Pi_{i+1}^{ m P}:Sigma_i^{ m P} = { m co}Pi_{i}^{ m P}
Unlike the arithmetic and analytic hierarchies, whose inclusions are known to be proper, it is an open question whether any of these inclusions are proper, though it is widely believed that they all are. If any Sigma_k^{ m P} = Sigma_{k+1}^{ m P}, or if any Sigma_k^{ m P} = Pi_{k}^{ m P}, then the hierarchy "collapses to level k": for all i > k, Sigma_i^{ m P} = Sigma_k^{ m P}. In particular, if P = NP, then the hierarchy collapses completely.
The union of all classes in the polynomial hierarchy is the complexity class PH.
The polynomial hierarchy is an analogue (at much lower complexity) of the
exponential hierarchy andarithmetical hierarchy .It is known that PH is contained within
PSPACE , but it is not known whether the two classes are equal. One useful reformulation of this problem is that PH = PSPACE if and only ifsecond-order logic gains no additional power from the addition of atransitive closure operator.If the polynomial hierarchy has any
complete problem s, then it has only finitely many distinct levels. Since there arePSPACE-complete problems, we know that if PSPACE = PH, then the polynomial hierarchy must collapse, since a PSPACE-complete problem would be a Sigma_{k}^{ m P}-complete problem for some "k".Each class in the polynomial hierarchy contains leq_{ m m}^{ m P}-complete problems (problems complete under polynomial-time many-one reductions). Furthermore, each class in the polynomial hierarchy is "closed under leq_{ m m}^{ m P}-reductions": meaning that for a class mathcal{C} in the hierarchy and a language L in mathcal{C}, if A leq_{ m m}^{ m P} L, then A in mathcal{C} as well. These two facts together imply that if K_i is a complete problem for Sigma_{i}^{ m P}, then Sigma_{i+1}^{ m P} = left( Sigma_{i}^{ m P} ight)^{K_i}, and Pi_{i+1}^{ m P} = left( Pi_{i}^{ m P} ight)^{K_i^{ m c. For instance, Sigma_{2}^{ m P} = { m NP}^{ m SAT}. In other words, if a language is defined based on some oracle in mathcal{C}, then we can assume that it is defined based on a complete problem for mathcal{C}. Complete problems therefore act as "representatives" of the class for which they are complete.
Problems in the polynomial hierarchy
- An example of a natural problem in Sigma_2^P is "circuit minimization": given a number "k" and a circuit "A" computing a
Boolean function "f", determine if there is a circuit with at most "k" gates that computes the same function "f". Let mathcal{C} be the set of all boolean circuits. The language:L = left{ langle A,k,B,x angle in mathcal{C} imes mathbb{N} imes mathcal{C} imes {0,1}^* left
B mbox{ has at most } k mbox{ gates, and } A(x)=B(x) ight. ight}is decidable in polynomial time. The language
:mathit{CM} = left{ langle A,k angle in mathcal{C} imes mathbb{N} left| egin{matrix}mbox{there exists a circuit } B mbox{ with at most } k mbox{ gates } \mbox{ such that } A mbox{ and } B mbox{ compute the same function} end{matrix} ight. ight}
is the circuit minimization language. mathit{CM} in Sigma_2^P (= exists^{ m P} forall^{ m P} { m P}) because L is decidable in polynomial time and because, given langle A,k angle , langle A,k angle in mathit{CM} if and only if "there exists" a circuit B such that "for all" inputs x, langle A,k,B,x angle in L .
- A complete problem for Sigma_k^{
m P} is satisfiability for quantified Boolean formulas with "k" alternations of quantifiers (abbreviated QBFk or QSATk). This is the version of the
boolean satisfiability problem for Sigma_k^{ m P}. In this problem, we are given a Boolean formula "f" with variables partitioned into "k" sets "X1", ..., "Xk". We have to determine if it is true that :exists X_1 forall X_2 exists X_3 ldots fThat is, is there an assignment of values to variables in "X1" such that, for all assignments of values in "X2", there exists an assignment of values to variables in "X3", ... "f" is true?The variant above is complete for Sigma_k^{ m P}. The variant in which the first quantifier is "for all", the second is "exists", etc., is complete for Pi_k^{ m P}.
See also
*
EXPTIME References
# A. R. Meyer and L. J. Stockmeyer. The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space. "In Proceedings of the 13th IEEE Symposium on Switching and Automata Theory", pp. 125–129, 1972. The paper that introduced the polynomial hierarchy.
# L. J. Stockmeyer. [http://dx.doi.org/10.1016/0304-3975(76)90061-X The polynomial-time hierarchy] . "Theoretical Computer Science", vol.3, pp.1–22, 1976.
# C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Chapter 17. "Polynomial hierarchy", pp. 409–438.
# Section 7.2: The Polynomial Hierarchy, pp.161–167.- For the oracle definition of the polynomial hierarchy, define
Wikimedia Foundation. 2010.