YP except the advice string s_n can be verified in polynomial time without needing the input x [AD14].
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].
Is to YQP as YP* is to YP [AD14].
Is contained in APP, and so is low for PP [Yir24].