PH complexity

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 is contained in the complexity classes P^PP (the class of problems that are decidable by a polynomial time Turing machine with an access to PP oracle) and PSPACE.

Important complexity classes

P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | NC | P-C

PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH

es:PH (clase de complejidad)

Categories: Complexity classes

This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia article. Browse Wikipedia for more information.