PH (complexity)

From Wikipedia, the free encyclopedia

In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy:

${\mbox{PH}}=\bigcup _{{k\in {\mathbb {N}}}}\Delta _{k}{\mbox{P}}$

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 = P^PP (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.

References

Larry J. Stockmeyer, "The polynomial hierarchy", Theoretical Computer Science, Vol. 3 (1976), pp. 1–22.
Scott Aaronson, BQP and the Polynomial Hierarchy, ACM STOC (2010), arXiv:0910.4698, ECCC TR09-104.
Complexity Zoo: PH

v t e Important complexity classes (more)

Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP

Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete

Considered infeasible	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL

Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy

Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.