Polynomial hierarchy
Encyclopedia
In computational complexity theory
, the polynomial hierarchy is a hierarchy
of complexity class
es that generalize the classes P
, NP
and co-NP to oracle machine
s. It is a resource-bounded counterpart to the arithmetical hierarchy
and analytical hierarchy
from mathematical logic
.
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
, or if any 
, then the hierarchy collapses to level k: for all 
, 
. In particular, if P = NP, then the hierarchy collapses completely.
The union of all classes in the polynomial hierarchy is the complexity class PH.
.
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 if second-order logic over finite structures
gains no additional power from the addition of a transitive closure
operator.
If the polynomial hierarchy has any complete problems, then it has only finitely many distinct levels. Since there are PSPACE-complete
problems, we know that if PSPACE = PH, then the polynomial hierarchy must collapse, since a PSPACE-complete problem would be a
-complete problem for some k.
Each class in the polynomial hierarchy contains
-complete problems (problems complete under polynomial-time many-one reductions). Furthermore, each class in the polynomial hierarchy is closed under 
-reductions: meaning that for a class 
in the hierarchy and a language 
, if 
, then 
as well. These two facts together imply that if 
is a complete problem for 
, then 
, and 
. For instance, 
. 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 states that the class BPP is contained in second level of polynomial hierarchy.
Kannan's theorem states that for any k,
is not contained in SIZE(nk).
Toda's theorem
states that the polynomial hierarchy is contained in P#P.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the polynomial hierarchy is a hierarchy
Hierarchy (mathematics)
In mathematics, a hierarchy is a preorder, i.e. an ordered set. The term is used to stress a natural hierarchical relation among the elements. In particular, it is the preferred terminology for posets whose elements are classes of objects of increasing complexity. In that case, the preorder...
of complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
es that generalize the classes P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
, NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
and co-NP to oracle machine
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
s. It is a resource-bounded counterpart to the arithmetical hierarchy
Arithmetical hierarchy
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene-Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them...
and analytical hierarchy
Analytical hierarchy
In mathematical logic and descriptive set theory, the analytical hierarchy is a higher type analogue of the arithmetical hierarchy. It thus continues the classification of sets by the formulas that define them.-The analytical hierarchy of formulas:...
from mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
.
Definitions
There are multiple equivalent definitions of the classes of the polynomial hierarchy.
For the oracle definition of the polynomial hierarchy, define
where PP (complexity)In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
is the set of decision problemDecision problemIn computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s solvable in polynomial time. Then for i ≥ 0 define
where AB is the set of decision problemDecision problemIn computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s solvable by a Turing machineTuring machineA Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
in class A augmented by an oracleOracle machineIn complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
for some complete problem in class B. For example,
, and 
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
be a languageFormal languageA formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
(i.e. a decision problemDecision problemIn computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
, a subset of {0,1}*), let
be a polynomialPolynomialIn mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
, and define
where
is some standard encoding of the pair of binary strings x and w as a single binary string. L represents a set of ordered pairs of strings, where the first string x is a member of 
, and the second string w is a "short" (
) witness testifying that x is a member of 
. In other words, 
if and only if there exists a short witness w such that 
. Similarly, define
Note that De Morgan's Laws hold:
and 
, where Lc is the complement of L.
Let
be a class of languages. Extend these operators to work on whole classes of languages by the definition
Again, De Morgan's Laws hold:
and 
, where 
.
The classes NPNP (complexity)In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
and co-NP can be defined as
, and 
, where PP (complexity)In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
is the class of all feasibly (polynomial-time) decidable languages. The polynomial hierarchy can be defined recursively as
Note that
, and 
.
This definition reflects the close connection between the polynomial hierarchy and the arithmetical hierarchyArithmetical hierarchyIn mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene-Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them...
, where R and RERecursively enumerable languageIn mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing-acceptable. It is known as a type-0 language in the Chomsky hierarchy of formal languages...
play roles analogous to PP (complexity)In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
and NPNP (complexity)In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
, respectively. The analytic 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 machineAlternating Turing machineIn computational complexity theory, an alternating Turing machine is a non-deterministic Turing machine with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP...
s defines
(respectively, 
) as the set of decision problems solvable in polynomial time on an alternating Turing machine with 
alternations starting in an existential (respectively, universal) state.
Relations between classes in the polynomial hierarchy
The definitions imply the relations: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
, or if any , then the hierarchy collapses to level k: for all , . In particular, if P = NP, then the hierarchy collapses completely.The union of all classes in the polynomial hierarchy is the complexity class PH.
Properties
The polynomial hierarchy is an analogue (at much lower complexity) of the exponential hierarchy and arithmetical hierarchyArithmetical hierarchy
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene-Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them...
.
It is known that PH is contained within PSPACE
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
, 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
SO (complexity)
Second-order logic is an extenstion of first-order with second orders quantifiers, hence the reader should first read FO to be able to understand this article. In descriptive complexity we can see that the languages recognised by SO formulae is exactly equal to the language decided by a Turing...
gains no additional power from the addition of a transitive closure
Transitive closure
In mathematics, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal . If the binary relation itself is transitive, then the transitive closure will be that same binary relation; otherwise, the transitive closure...
operator.
If the polynomial hierarchy has any complete problems, then it has only finitely many distinct levels. Since there are PSPACE-complete
PSPACE-complete
In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time...
problems, we know that if PSPACE = PH, then the polynomial hierarchy must collapse, since a PSPACE-complete problem would be a
-complete problem for some k.Each class in the polynomial hierarchy contains
-complete problems (problems complete under polynomial-time many-one reductions). Furthermore, each class in the polynomial hierarchy is closed under -reductions: meaning that for a class in the hierarchy and a language , if , then as well. These two facts together imply that if is a complete problem for , then , and . For instance, . 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 states that the class BPP is contained in second level of polynomial hierarchy.
Kannan's theorem states that for any k,
is not contained in SIZE(nk).Toda's theorem
Toda's theorem
Toda's theorem was proven by Seinosuke Toda in his paper "PP is as Hard as the Polynomial-Time Hierarchy" and was given the 1998 Gödel Prize. The theorem states that the entire polynomial hierarchy PH is contained in PPP; this implies a closely related statement, that PH is contained in P#P...
states that the polynomial hierarchy is contained in P#P.
Problems in the polynomial hierarchy
An example of a natural problem in
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 
be the set of all boolean circuits. The language
is decidable in polynomial time. The language
is the circuit minimization language.
because 
is decidable in polynomial time and because, given 
, 
if and only if there exists a circuit 
such that for all inputs 
, 
.
A complete problem for
is satisfiability for quantified Boolean formulas with k alternations of quantifiers (abbreviated QBFk or QSATk). This is the version of the boolean satisfiability problemBoolean satisfiability problemIn computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
for
. 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
That 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
. The variant in which the first quantifier is "for all", the second is "exists", etc., is complete for 
.