Class Description

YP*: Yaroslav-Percival Star

YP except the advice string s_n can be verified in polynomial time without needing the input x [AD14].

Linked From

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

YQP*: Yaroslav BQP star

Is to YQP as YP* is to YP [AD14].

Is contained in APP, and so is low for PP [Yir24].

More about...