# Difference between revisions of "Complexity Zoo:Y"

m (1 revision: Complexity zoo import.) |
m (→YP: Your Polynomial-Time or Yaroslav-Percival: update link) |
||

Line 13: | Line 13: | ||

<li>For all inputs x and advice strings s, M(x,s) outputs either the correct answer or "I don't know."</li> | <li>For all inputs x and advice strings s, M(x,s) outputs either the correct answer or "I don't know."</li> | ||

</ul> | </ul> | ||

− | Defined in a [http://www. | + | Defined in a [http://www.scottaaronson.com/blog/?p=77 recent post] of the blog [http://www.scottaaronson.com/blog/ Shtetl-Optimized]. See there for an explanation of the class's name. |

Contains [[Complexity Zoo:Z#zpp|ZPP]] by the same argument that places [[Complexity Zoo:B#bpp|BPP]] in [[Complexity Zoo:P#ppoly|P/poly]]. | Contains [[Complexity Zoo:Z#zpp|ZPP]] by the same argument that places [[Complexity Zoo:B#bpp|BPP]] in [[Complexity Zoo:P#ppoly|P/poly]]. |

## Revision as of 22:49, 11 July 2013

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

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