Class Description

YP: Your Polynomial-Time or Yaroslav-Percival

The class of decision problems for which there exists a polynomial-time machine M such that:

Defined in a recent post of the blog Shtetl-Optimized. See there for an explanation of the class's name.

Contains ZPP by the same argument that places BPP in P/poly.

Also contains P with TALLYNPcoNP oracle.

Is contained in NP ∩ coNP and YPP.

Is equal to ONP ∩ coONP.

Linked From

ONP: Oblivious NP

The class of functions computable in polynomial time with a shared, untrusted witness for each input size. The input-oblivious version of NP.

L is in ONP if there exists a polynomial time verifier V taking an input and a witness, so that:

  1. There is a witness for each n of polynomial size, so that for any input of size n, if the input is in L, then the verifier accepts on that input and the witness.
  2. If the input is not in L, then for any witness, the verifier rejects on that input.

Defined in [FSW09], where it was shown NP has size nk circuits for some constant k if and only if ONP/1 has size nj circuits for some constant j.

ONP is contained in P/poly and NP [FSW09].

ONP = NP iff NP is in P/poly [FSW09].

If NE is not E then ONP is not P [GM15].

See also YP for an input oblivious analogue of NP ∩ coNP.

More about...


YP*: Yaroslav-Percival Star

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

More about...


YPP: Yaroslav BPP

The probabilistic analogue of YP; it is to YP what MA is to NP. Formally, the class of decision problems for which there exists a syntactic BPP machine M such that:

To amplify a YPP machine, one can run it multiple times, then accept if a majority of runs accept, reject if a majority reject, and otherwise output "I don't know."

Contains BPP and YP, and is contained in MA and P/poly.

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