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:

• For all input sizes n, there exists a polynomial-size advice string s_n such that M(x,s_n) outputs the correct answer for all inputs x of size n.
• For all inputs x and advice strings s, M(x,s) outputs either the correct answer or "I don't know."

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 TALLY ∩ NP ∩ coNP 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 n^k circuits for some constant k if and only if ONP/1 has size n^j 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:

• For all input sizes n, there exists a polynomial-size advice string a_n such that for all inputs x of size n, M(x,a_n) outputs the correct answer with probability at least 2/3.
• For all inputs x and advice strings a, the probability that M(x,a) outputs the incorrect answer is at most 1/3. In other words, the sum of the probabilities of the correct answer and "I don't know" is at least 2/3.

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