Class Description

P^NP[log]: P With Log NP Queries

Also known as Θ₂^P.

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

P^NP[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 P^NP[log] [HHR97].

Contains P^NP[k] for all constants k.

Linked From

BH: Boolean Hierarchy Over NP

The smallest class that contains NP and is closed under union, intersection, and complement.

The levels are defined as follows:

• BH₁ = NP.
• BH_2i is the class of languages that are the intersection of a BH_2i-1 language with a coNP language.
• BH_2i+1 is the class of languages that are the union of a BH_2i language with an NP language.

Then BH is the union over all i of BH_i.

Defined in [WW85].

For more detail see [CGH+88].

Contained in Δ₂P and indeed in P^NP[log].

If BH collapses at any level, then PH collapses to Σ₃P [Kad88].

See also: DP, QH.

More about...

BPP_path: Threshold BPP

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:

• BPP_path contains MA and P^NP[log], and is contained in PP and BPP^NP.
• BPP_path is closed under complementation, intersection, and union.
• If BPP_path = BPP_path^BPP_path, then PH collapses to BPP_path.
• If BPP_path contains Σ₂P, then PH collapses to BPP^NP.

There exists an oracle relative to which BPP_path is not contained in Σ₂P [BGM02].

An alternate characterization of BPP_path uses the idea of post-selection. That is, BPP_path is the class of languages ${\displaystyle L}$ for which there exists a pair of polynomial-time Turing machines ${\displaystyle A}$ and ${\displaystyle B}$ such that the following conditions hold for all ${\displaystyle x}$:

• If ${\displaystyle x\in L}$, ${\displaystyle \Pr _{r\in \{0,1\}^{\mathrm {poly} (\left\vert x\right\vert )}}\left[A(x,r)\mid B(x,r)\right]\geq {\frac {2}{3}}}$.
• If ${\displaystyle x\notin L}$, ${\displaystyle \Pr _{r\in \{0,1\}^{\mathrm {poly} (\left\vert x\right\vert )}}\left[A(x,r)\mid B(x,r)\right]<{\frac {1}{3}}}$.
• ${\displaystyle \Pr _{r\in \{0,1\}^{\mathrm {poly} (n)}}\left[B(x,r)\right]>0}$.

We say that ${\displaystyle B}$ 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 ⊆ BPP_path nearly trivial.

See Also: PostBQP (quantum analogue).

More about...

FP: Function Polynomial-Time

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 FP^NP = FP^NP[log] (that is, allowed only a logarithmic number of queries), then P = NP [Kre88]. The corresponding result for P^NP versus P^NP[log] is not known, and indeed fails relative to some oracles (see [Har87b]).

More about...

P^||NP: P With Parallel Queries To NP

Equals P^NP[log] ([BH91] and [Hem89] independently).

More about...

P^NP[k]: P With k NP Queries(for constant k)

Equals P with 2^k-1 parallel queries to NP (i.e. queries that do not depend on the outcomes of previous queries) ([BH91] and [Hem89] independently).

If P^NP[1] = P^NP[2], then P^NP[1] = P^NP[log] and indeed PH collapses to Δ₃P (attributed in [Har87b] to J. Kadin).

More about...

P^{NP[log^2]}: P With Log² NP Queries

Same as P^NP[log], except that now log² queries can be made.

The model-checking problem for a certain temporal logic is P^{NP[log^2]}-complete [Sch03].

For all k ≥ 1, P with log^k adaptive queries to NP coincides with P with log^k−1 rounds of (polynomially many) nonadaptive queries [CS92].

More about...

PP: Probabilistic Polynomial-Time

The class of decision problems solvable by an NP machine such that

1. If the answer is 'yes' then at least 1/2 of computation paths accept.
2. If the answer is 'no' then less than 1/2 of computation paths accept.

Defined in [Gil77].

PP is closed under union and intersection [BRS91] (this was an open problem for 14 years). More generally, P^PP[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 P^NP[log] [BHW89] and QMA (see [MW05]). However, there exists an oracle relative to which PP does not contain Δ₂P [Bei94].

PH is in P^PP [Tod89].

BPP [KST+89b] and even BQP [FR98] and YQP* [Yir24] are low for PP: i.e., PP^BQP = PP.
APP is PP-low [Li93].

Equals PostBQP [Aar05b].

For a random oracle A, PP^A is strictly contained in PSPACE^A with probability 1 [ABF+94].

For any fixed k, there exists a language in PP that does not have circuits of size n^k [Vin04b].
Indeed, there exists a language in PP that does not even have quantum circuits of size n^k 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.

More about...

Θ₂P: Alternate name for P^NP[log]

More about...