Class Description

APP: Amplified PP

Roughly, the class of decision problems for which the following holds. For all polynomials p(n), there exist GapP functions f and g such that for all inputs x with n=|x|,

  1. If the answer is "yes" then 1 > f(x)/g(1n) > 1-2-p(n).
  2. If the answer is "no" then 0 < f(x)/g(1n) < 2-p(n).

Defined in [Li93], where the following was also shown:

APP contains AWPP [Fen02].

The abbreviation APP is also used for Approximable in Probabilistic Polynomial Time, see AxPP.

Contains FewP [Li93] and contains YQP*, YMA*, and YP* [Yir24].

Linked From

AWPP: Almost WPP

The class of decision problems solvable by an NP machine such that for some polynomial-time computable (i.e. FP) function f,

  1. If the answer is "no," then the difference between the number of accepting and rejecting paths is non-negative and at most 2-poly(n)f(x).
  2. If the answer is "yes," then the difference is between (1-2-poly(n))f(x) and f(x).

Defined in [FFK94].

Contains BQP [FR98], WAPP [BGM02], LWPP, and WPP.

Contained in APP [Fen02].

More about...


AxPP: Approximable in Probabilistic Polynomial Time

Usually called APP. I've renamed it AxPP to distinguish it from the "other" APP.

The class of real-valued functions from {0,1}n to [0,1] that can be approximated within any ε>0 by a probabilistic Turing machine in time polynomial in n and 1/ε.

Defined by [KRC00], who also show the following:

AxPP is recursively enumerable [Jeř07].

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

PH is in PPP [Tod89].

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

Equals PostBQP [Aar05b].

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.

More about...


YQP*: Yaroslav BQP star

Is to YQP as YP* is to YP [AD14].

Is contained in APP, and so is low for PP [Yir24].

More about...