Class Description

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

Linked From

A0PP: One-Sided Analog of AWPP

Same as SBP, except that f is a nonnegative-valued GapP function rather than a #P function.

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

Kuperberg ([Kup09]) showed that A0PP = SBQP.

More about...


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

More about...


BQP: Bounded-Error Quantum Polynomial-Time

The class of decision problems solvable in polynomial time by a quantum Turing machine, with at most 1/3 probability of error.

One can equivalently define BQP as the class of decision problems solvable by a uniform family of polynomial-size quantum circuits, with at most 1/3 probability of error [Yao93]. Any universal gate set can be used as a basis; however, a technicality is that the transition amplitudes must be efficiently computable, since otherwise one could use them to encode the solutions to hard problems (see [ADH97]).

BQP is often identified as the class of feasible problems for quantum computers.

Contains the factoring and discrete logarithm problems [Sho97], the hidden Legendre symbol problem [DHI02], the Pell's equation and principal ideal problems [Hal02], and some other problems not thought to be in BPP.

Defined in [BV97], where it is also shown that BQP contains BPP and is contained in P with a #P oracle.

BQPBQP = BQP [BV97].

[ADH97] showed that BQP is contained in PP, and [FR98] showed that BQP is contained in AWPP.

There exist oracles relative to which:

If P=BQP relative to a random oracle then BQP=BPP [FR98].

More about...


LWPP: Length-Dependent Wide PP

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

  1. If the answer is "no," then the number of accepting computation paths exactly equals the number of rejecting paths.
  2. If the answer is "yes," then the difference of these numbers equals a function f(|x|) computable in polynomial time (i.e. FP). Here |x| is the length of the input x, and ``polynomial time means polynomial in |x|, the length of x, rather than the length of |x|.

Defined in [FFK94], where it was also shown that LWPP is low for PP and C=P. (I.e. adding LWPP as an oracle does not increase the power of these classes.)

Contained in WPP and AWPP.

Contains SPP.

Also, contains the graph isomorphism problem [KST92].

Contains a whole litter of problems for solvable black-box groups: group intersection, group factorization, coset intersection, and double-coset membership [Vin04].

More about...


WAPP: Weak Almost-Wide PP

The class of decision problems for which there exists a #P function f, a polynomial p, and an ε > 0, such that for all inputs x,

  1. If the answer is "yes" then 2p(|x|) ≥ f(x) > (1+ε) 2p(|x|)-1.
  2. If the answer is "no" then 0 ≤ f(x) < (1-ε) 2p(|x|)-1.

Defined in [BGM02], where it is also shown that WAPP is contained in AWPP and SBP.

More about...


WPP: Wide PP

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

  1. If the answer is "no," then the number of accepting computation paths exactly equals the number of rejecting paths.
  2. If the answer is "yes," then their difference exactly equals a function f(x) computable in polynomial time (i.e. FP).

Defined in [FFK94].

Contained in C=PcoC=P, as well as AWPP.

Contains SPP and LWPP.

More about...