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


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