# Difference between revisions of "Complexity Zoo:Y"

m (→YP: Your Polynomial-Time or Yaroslav-Percival: update link) |
|||

Line 20: | Line 20: | ||

Is contained in [[Complexity Zoo:N#npiconp|NP ∩ coNP]] and [[#ypp|YPP]]. | Is contained in [[Complexity Zoo:N#npiconp|NP ∩ coNP]] and [[#ypp|YPP]]. | ||

+ | |||

+ | Is equal to [[Complexity Zoo:O#onp|ONP]] ∩ coONP. | ||

---- | ---- |

## Latest revision as of 21:57, 27 May 2021

*Back to the Main Zoo* -
*Complexity Garden* -
*Zoo Glossary* -
*Zoo References*

*Complexity classes by letter:*
Symbols -
A -
B -
C -
D -
E -
F -
G -
H -
I -
J -
K -
L -
M -
N -
O -
P -
Q -
R -
S -
T -
U -
V -
W -
X -
Y -
Z

*Lists of related classes:*
Communication Complexity -
Hierarchies -
Nonuniform

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

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

##### YQP: Yaroslav BQP

Is to YPP as BQP is to BPP, and QMA is to MA. The machine is now a quantum computer and the advice is a quantum state |ψ_n>.

Contains BQP and YPP, and is contained in QMA and BQP/qpoly.