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