DTIME: Difference between revisions
en>Rjwilmsi m →Generalizations: Format plain DOIs using AWB (8060) |
en>Addbot m Bot: Migrating 7 interwiki links, now provided by Wikidata on d:q1155831 (Report Errors) |
||
| Line 1: | Line 1: | ||
In [[computational complexity theory]], the [[complexity class]] '''PH''' is the union of all complexity classes in the [[polynomial hierarchy]]: | |||
:<math>\mbox{PH} = \bigcup_{k\in\mathbb{N}} \Delta_k\mbox{P}</math> | |||
'''PH''' was first defined by [[Larry Stockmeyer]]. It is a special case of hierarchy of [[Alternating_Turing_machine#Bounded_alternation|bounded alternating Turing machine]]. It is contained in '''P<sup>#P</sup>''' = '''P<sup>PP</sup>''' (by [[Toda's theorem]]; the class of problems that are decidable by a polynomial time [[Turing machine]] with access to a [[Sharp P|#P]] or equivalently [[PP (complexity class)|PP]] [[oracle machine|oracle]]), and also in '''[[PSPACE]]'''. | |||
'''PH''' has a simple [[descriptive complexity|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 (complexity)|P]]''', '''[[NP (complexity)|NP]]''', and '''[[co-NP]]'''. It even contains probabilistic classes such as '''[[Bounded-error probabilistic polynomial|BPP]]''' and '''[[RP (complexity)|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|2009|09|104}}. | |||
*{{CZoo|PH|P#ph}} | |||
{{ComplexityClasses}} | |||
[[Category:Complexity classes]] | |||
{{comp-sci-theory-stub}} | |||
Revision as of 07:43, 26 February 2013
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.
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), Template:Arxiv, Template:ECCC.
- Template:CZoo
Hi generally. Let me start by introducing the author, his name is Benjamin Cassity and he totally digs that address. To climb is a thing that we're totally dependent on. California is where her house is but now she is considering additional. After being beyond his part of years he became a postal service worker. See what's new on my website here: http://devolro.com/diablo-gallery
Look at my web blog :: cars