PH (complexity)
Encyclopedia
In computational complexity theory
, the complexity class
PH is the union of all complexity classes in the polynomial hierarchy
:
PH was first defined by Larry Stockmeyer
. It is a special case of hierarchy of bounded alternating Turing machine. It is contained in P#P = PPP (by Toda's theorem
; the class of problems that are decidable by a polynomial time Turing machine
with access to a #P or equivalently PP oracle
), and also in PSPACE
.
PH has a simple logical characterization
: it is the set of languages expressible by second-order logic
.
PH contains almost all well-known complexity classes inside PSPACE; in particular, it contains P
, NP
, and co-NP. It even contains probabilistic classes such as BPP and RP
. However, there is some evidence that BQP
, the class of problems solvable in polynomial time by a quantum computer
, is not contained in PH (Aaronson 2010).
P = NP if and only if P = PH. This may simplify a potential proof of P ≠ NP, since it's only necessary to separate P from the more general class PH.
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 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:...
PH is the union of all complexity classes in the polynomial hierarchy
Polynomial hierarchy
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines...
:
PH was first defined by Larry Stockmeyer
Larry Stockmeyer
Larry Joseph Stockmeyer was a computer scientist. He was one of the pioneers in the field of computational complexity theory, and he also worked in the field of distributed computing...
. It is a special case of hierarchy of bounded alternating Turing machine. It is contained in P#P = PPP (by 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...
; the class of problems that are decidable by a polynomial time Turing machine
Turing machine
A 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...
with access to a #P or equivalently PP oracle
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...
), and also in 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 :...
.
PH has a simple logical characterization
Descriptive complexity
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the...
: it is the set of languages expressible by second-order logic
Second-order logic
In logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory....
.
PH contains almost all well-known complexity classes inside PSPACE; in particular, it contains 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. It even contains probabilistic classes such as BPP and RP
RP (complexity)
In complexity theory, RP is the complexity class of problems for which a probabilistic Turing machine exists with these properties:* It always runs in polynomial time in the input size...
. However, there is some evidence that BQP
BQP
In computational complexity theory BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances...
, the class of problems solvable in polynomial time by a quantum computer
Quantum computer
A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...
, is not contained in PH (Aaronson 2010).
P = NP if and only if P = PH. This may simplify a potential proof of P ≠ NP, since it's only necessary to separate P from the more general class PH.