YACC: Yet Another Complexity Class
A term of derision, used against a complexity class.
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 sn such that M(x,sn) 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."
Is equal to ONP ∩ coONP.
YPP: Yaroslav BPP
- For all input sizes n, there exists a polynomial-size advice string an such that for all inputs x of size n, M(x,an) 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."