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. 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.

<< Previous

Word Browser

Next >>

dtime
ntime
focal (hp 41)
mark lanegan
p (complexity)
rainis
toyota mr2
the book of the duchess
ilya yefimovich repin
steven smith (astronaut)
steven smith

tilman riemenschneider
gerousia
anthraquinone
ntm
andrei rublev
dtm
list of swimming coaches
mass (disambiguation)
cls (computing)
rudaki
doskey

doug frost
cascar
jay c. buckey
don gambril
richard quick
justice bomb
ave verum corpus
frederick w. sturckow
bill sweetenham
twintext
vladimir n. dezhurov

state (physics)
cahors
shii ann huang
barry b. longyear
polynomial hierarchy
ghandia johnson
helmuts balderis
saturday night live cast
shemp howard
sinistral
dextral