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

A₀PP: 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:

• A₀PP contains QMA, AWPP, and coC₌P.
• A₀PP is contained in PP.
• If A₀PP = PP then PH is contained in PP.

Kuperberg ([Kup09]) showed that A₀PP = 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(1ⁿ) > 1-2^-p(n).
2. If the answer is "no" then 0 < f(x)/g(1ⁿ) < 2^-p(n).

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

• APP is contained in PP, and indeed is low for PP.
• APP is closed under intersection, union, and complement.

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.

BQP^BQP = 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:

• BQP does not equal to BPP [BV97] (and by similar arguments, is not in P/poly).
• BQP is not contained in MA [Wat00].
• BQP is not contained in PH [RT18] (see also [Wu18]).
• BQP is not contained in Mod_pP for prime p [GV02].
• NP, and indeed NP ∩ coNP, are not contained in BQP with probability 1 relative to a random oracle and a random permutation oracle, respectively [BBB+97].
• SZK is not contained in BQP [Aar02].
• BQP is not contained in SZK (follows easily using the quantum walk problem in [CCD+03]).
• BQP is not contained in BPP_path [Aar10] (see also [Che16]).
• PPAD is not contained in BQP [Li11].
• P=BQP and PH is infinite [FR98].

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 2^p(|x|) ≥ f(x) > (1+ε) 2^p(|x|)-1.
2. If the answer is "no" then 0 ≤ f(x) < (1-ε) 2^p(|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₌P ∩ coC₌P, as well as AWPP.

Contains SPP and LWPP.

More about...