Class Description

GapP: Gap Polynomial-Time

The class of functions f(x) such that for some NP machine, f(x) is the number of accepting paths minus the number of rejecting paths.

Equivalently, the closure of the #P functions under subtraction.

Defined in [FFK94] and independently [Gup95].

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


GapL: Gap Logarithmic-Space

Has the same relation to L as GapP does to P. (And therefore, has the same relation to #L as GapP does to #P.)

The determinant is GapL-complete [Vin91] [Dam91] [Tod91] ([MV97] also gave a new, self-contained proof). See also the corresponding decision class DET

More about...