Also known as Θ2P.
The class of decision problems solvable by a P machine, that can make O(log n) queries to an NP oracle (where n is the length of the input).
Equals P||NP, the class of decision problems solvable by a P machine that can make polynomially many nonadaptive queries to an NP oracle (i.e. queries that do not depend on the outcomes of previous queries) ([BH91] and [Hem89] independently).
PNP[log] is contained in PP [BHW89].
Determining the winner in an election system proposed in 1876 by Charles Dodgson (a.k.a. Lewis Carroll) has been shown to be complete for PNP[log] [HHR97].
Contains PNP[k] for all constants k.
The smallest class that contains NP and is closed under union, intersection, and complement.
The levels are defined as follows:
Then BH is the union over all i of BHi.
Defined in [WW85].
For more detail see [CGH+88].
Contained in Δ2P and indeed in PNP[log].
If BH collapses at any level, then PH collapses to Σ3P [Kad88].
Same as BPP, except that now the computation paths need not all have the same length.
Defined in [HHT97], where the following was also shown:
There exists an oracle relative to which BPPpath is not contained in Σ2P [BGM02].
An alternate characterization of BPPpath uses the idea of post-selection. That is, BPPpath is the class of languages for which there exists a pair of polynomial-time Turing machines and such that the following conditions hold for all :
We say that is the post-selector. Intuitively, this characterization allows a BPP machine to require that its random bits have some special but easily verifiable property. This characterization makes the inclusion NP ⊆ BPPpath nearly trivial.
See Also: PostBQP (quantum analogue).
Sometimes defined as the class of functions computable in polynomial time by a Turing machine. (Generalizes P, which is defined in terms of decision problems only.)
However, if we want to compare FP to FNP, we should instead define it as the class of FNP problems (that is, polynomial-time predicates P(x,y)) for which there exists a polynomial-time algorithm that, given x, outputs any y such that P(x,y). That is, there could be more than one valid output, even though any given algorithm only returns one of them.
FP = FNP if and only if P = NP.
If FPNP = FPNP[log] (that is, allowed only a logarithmic number of queries), then P = NP [Kre88]. The corresponding result for PNP versus PNP[log] is not known, and indeed fails relative to some oracles (see [Har87b]).
Equals PNP[log] ([BH91] and [Hem89] independently).
Equals P with 2k-1 parallel queries to NP (i.e. queries that do not depend on the outcomes of previous queries) ([BH91] and [Hem89] independently).
If PNP[1] = PNP[2], then PNP[1] = PNP[log] and indeed PH collapses to Δ3P (attributed in [Har87b] to J. Kadin).
Same as PNP[log], except that now log2 queries can be made.
The model-checking problem for a certain temporal logic is PNP[log^2]-complete [Sch03].
For all k ≥ 1, P with logk adaptive queries to NP coincides with P with logk−1 rounds of (polynomially many) nonadaptive queries [CS92].
The class of decision problems solvable by an NP machine such that
Defined in [Gil77].
PP is closed under union and intersection [BRS91] (this was an open problem for 14 years). More generally, PPP[log] = PP. Even more generally, PP is closed under polynomial-time truth-table reductions, or even k-round reductions for any constant k [FR96].
Contains PNP[log] [BHW89] and QMA (see [MW05]). However, there exists an oracle relative to which PP does not contain Δ2P [Bei94].
BPP [KST+89b] and even BQP [FR98] and YQP* [Yir24] are low for PP: i.e., PPBQP = PP.
APP is PP-low [Li93].
For a random oracle A, PPA is strictly contained in PSPACEA with probability 1 [ABF+94].
For any fixed k, there exists a language in PP that does not have circuits of size nk [Vin04b].
Indeed, there exists a language in PP that does not even have quantum circuits of size nk with quantum advice [Aar06] and [Yir24].
By contrast, there exists an oracle relative to which PP has linear-size circuits [Aar06].
PP can be generalized to the counting hierarchy CH.