HOME

TheInfoList



OR:

In
computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a
hierarchy A hierarchy (from Ancient Greek, Greek: , from , 'president of sacred rites') is an arrangement of items (objects, names, values, categories, etc.) that are represented as being "above", "below", or "at the same level as" one another. Hierarchy ...
of
complexity class In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...
es that generalize the classes NP and co-NP. Each class in the hierarchy is contained within
PSPACE In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''f''(''n'')), the set of all problems that can ...
. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the
arithmetical hierarchy In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...
and
analytical hierarchy Analytic or analytical may refer to: Chemistry * Analytical chemistry, the analysis of material samples to learn their chemical composition and structure * Analytical technique, a method that is used to determine the concentration of a chemica ...
from
mathematical logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
. The union of the classes in the hierarchy is denoted PH. Classes within the hierarchy have complete problems (with respect to
polynomial-time reduction In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another. One shows that if a hypothetical subroutine solving the second problem exists, then the first problem can be solved by transforming ...
s) that ask if quantified Boolean formulae hold, for formulae with restrictions on the quantifier order. It is known that equality between classes on the same level or consecutive levels in the hierarchy would imply a "collapse" of the hierarchy to that level.


Definitions

There are multiple equivalent definitions of the classes of the polynomial hierarchy.


Oracle definition

For the oracle definition of the polynomial hierarchy, define :\Delta_0^\mathrm := \Sigma_0^\mathrm := \Pi_0^\mathrm := \mathrm, where P is the set of
decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
s solvable in
polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
. Then for i ≥ 0 define :\Delta_^\mathrm := \mathrm^ :\Sigma_^\mathrm := \mathrm^ :\Pi_^\mathrm := \mathrm^ where \mathrm^ is the set of
decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
s solvable in polynomial time by a
Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
augmented by an
oracle An oracle is a person or thing considered to provide insight, wise counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. If done through occultic means, it is a form of divination. Descript ...
for some complete problem in class A; the classes \mathrm^ and \mathrm^ are defined analogously. For example, \Sigma_1^\mathrm = \mathrm, \Pi_1^\mathrm = \mathrm , and \Delta_2^\mathrm = \mathrm is the class of problems solvable in polynomial time by a deterministic Turing machine with an oracle for some NP-complete problem.


Quantified Boolean formulae definition

For the existential/universal definition of the polynomial hierarchy, let be a
language Language is a structured system of communication that consists of grammar and vocabulary. It is the primary means by which humans convey meaning, both in spoken and signed language, signed forms, and may also be conveyed through writing syste ...
(i.e. a
decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
, a subset of *), let be a
polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
, and define : \exists^p L := \left\, where \langle x,w \rangle \in \^* is some standard encoding of the pair of binary strings ''x'' and ''w'' as a single binary string. The language ''L'' represents a set of ordered 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 \rangle \in L . Similarly, define : \forall^p L := \left\ Note that
De Morgan's laws In propositional calculus, propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both Validity (logic), valid rule of inference, rules of inference. They are nam ...
hold: \left( \exists^p L \right)^ = \forall^p L^ and \left( \forall^p L \right)^ = \exists^p L^ , where ''L''c is the complement of ''L''. Let be a class of languages. Extend these operators to work on whole classes of languages by the definition :\exists^\mathrm \mathcal := \left\ :\forall^\mathrm \mathcal := \left\ Again, De Morgan's laws hold: \mathrm \exists^\mathrm \mathcal = \forall^\mathrm \mathrm \mathcal and \mathrm \forall^\mathrm \mathcal = \exists^\mathrm \mathrm \mathcal , where \mathrm\mathcal = \left\. The classes NP and co-NP can be defined as \mathrm = \exists^\mathrm \mathrm , and \mathrm = \forall^\mathrm \mathrm , where P is the class of all feasibly (polynomial-time) decidable languages. The polynomial hierarchy can be defined recursively as : \Sigma_0^\mathrm := \Pi_0^\mathrm := \mathrm : \Sigma_^\mathrm := \exists^\mathrm \Pi_k^\mathrm : \Pi_^\mathrm := \forall^\mathrm \Sigma_k^\mathrm Note that \mathrm = \Sigma_1^\mathrm , and \mathrm = \Pi_1^\mathrm . This definition reflects the close connection between the polynomial hierarchy and the
arithmetical hierarchy In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...
, where R and RE play roles analogous to P and NP, respectively. The analytic hierarchy is also defined in a similar way to give a hierarchy of subsets of the
real number In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...
s.


Alternating Turing machines definition

An alternating Turing machine is a non-deterministic Turing machine with non-final states partitioned into existential and universal states. It is eventually accepting from its current configuration if: it is in an existential state and can transition into some eventually accepting configuration; or, it is in a universal state and every transition is into some eventually accepting configuration; or, it is in an accepting state. We define \Sigma_k^\mathrm to be the class of languages accepted by an alternating Turing machine in polynomial time such that the initial state is an existential state and every path the machine can take swaps at most ''k'' – 1 times between existential and universal states. We define \Pi_k^\mathrm similarly, except that the initial state is a universal state. If we omit the requirement of at most ''k'' – 1 swaps between the existential and universal states, so that we only require that our alternating Turing machine runs in polynomial time, then we have the definition of the class AP, which is equal to
PSPACE In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''f''(''n'')), the set of all problems that can ...
.


Relations between classes in the polynomial hierarchy

The union of all classes in the polynomial hierarchy is the complexity class PH. The definitions imply the relations: :\Sigma_i^\mathrm \subseteq \Delta_^\mathrm \subseteq \Sigma_^\mathrm :\Pi_i^\mathrm \subseteq \Delta_^\mathrm \subseteq \Pi_^\mathrm :\Sigma_i^\mathrm = \mathrm\Pi_^\mathrm 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^\mathrm = \Sigma_^\mathrm, or if any \Sigma_k^\mathrm = \Pi_^\mathrm, then the hierarchy ''collapses to level k'': for all i > k, \Sigma_i^\mathrm = \Sigma_k^\mathrm. In particular, we have the following implications involving unsolved problems: * P = NP if and only if P = PH. * If NP = co-NP then NP = PH. (co-NP is \Pi_1^\mathrm.) The case in which NP = PH is also termed as a ''collapse'' of the PH to ''the second level''. The case P = NP corresponds to a collapse of PH to P. The question of collapse to the first level is generally thought to be extremely difficult. Most researchers do not believe in a collapse, even to the second level.


Relationships to other classes

The polynomial hierarchy is an analogue (at much lower complexity) of the exponential hierarchy and
arithmetical hierarchy In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...
. It is known that PH is contained within
PSPACE In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''f''(''n'')), the set of all problems that can ...
, but it is not known whether the two classes are equal. One useful reformulation of this problem is that PH = PSPACE if and only if second-order logic over finite structures gains no additional power from the addition of a
transitive closure In mathematics, the transitive closure of a homogeneous binary relation on a set (mathematics), set is the smallest Relation (mathematics), relation on that contains and is Transitive relation, transitive. For finite sets, "smallest" can be ...
operator over relations of relations (i.e., over the second-order variables). If the polynomial hierarchy has any
complete problem In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class. More formally, a problem ''p'' is called h ...
s, then it has only finitely many distinct levels. Since there are
PSPACE-complete In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (PSPACE, polynomial space) and if every other problem that can be solved in polynomial sp ...
problems, we know that if PSPACE = PH, then the polynomial hierarchy must collapse, since a PSPACE-complete problem would be a \Sigma_^\mathrm-complete problem for some ''k''. Each class in the polynomial hierarchy contains \leq_^\mathrm-complete problems (problems complete under polynomial-time many-one reductions). Furthermore, each class in the polynomial hierarchy is ''closed under \leq_^\mathrm-reductions'': meaning that for a class in the hierarchy and a language L \in \mathcal, if A \leq_^\mathrm L, then A \in \mathcal as well. These two facts together imply that if K_i is a complete problem for \Sigma_^\mathrm, then \Sigma_^\mathrm = \mathrm^, and \Pi_^\mathrm = \mathrm^. For instance, \Sigma_^\mathrm = \mathrm^\mathrm. In other words, if a language is defined based on some oracle in , then we can assume that it is defined based on a complete problem for . Complete problems therefore act as "representatives" of the class for which they are complete. * Sipser–Lautemann theorem: \mathrm \subset \Sigma_2^\mathrm \cap \Pi_2^\mathrm. * Kannan's theorem: \forall k, \Sigma_2 \not\subset \mathrm(n^k) . It is an open question whether \Sigma_2 \not\subset \bigcup_k \mathrm(n^k) = \mathrm . * Toda's theorem: \mathrm \subset \mathrm^ . There is some evidence that BQP, the class of problems solvable in polynomial time by a quantum computer, is not contained in PH; however, it is also believed that PH is not contained in BQP.=


Problems


See also

*
EXPTIME In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i.e., in O(2''p''(''n'')) time, w ...
* Exponential hierarchy * Arithmetic hierarchy


References


General 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. 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.


Citations

{{ComplexityClasses Mathematical logic hierarchies Complexity classes