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].
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.
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|,
Defined in [Li93], where the following was also shown:
The abbreviation APP is also used for Approximable in Probabilistic Polynomial Time, see AxPP.
Contains FewP [Li93] and contains YQP*, YMA*, and YP* [Yir24].
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