Science Fair Project Encyclopedia
PH (complexity)
In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy:
PH is contained in the complexity classes PPP (the class of problems that are decidable by a polynomial time Turing machine with an access to PP oracle) and 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.
If P = NP, then P = PH.
Last updated: 06-01-2005 22:37:27
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details