Difference between revisions of "Complexity Zoo:Y"
m (1 revision: Complexity zoo import.) |
|||
| (3 intermediate revisions by 3 users not shown) | |||
| 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]]. | ||
| 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. | ||
---- | ---- | ||
| + | ===== <span id="yp*" style="color:red">YP*</span>: Yaroslav-Percival Star ===== | ||
| + | [[Complexity Zoo:Y#yp|YP]] except the advice string s_n can be verified in polynomial time without needing the input x [[zooref#AD14|[AD14]]]. | ||
| + | |||
| + | ---- | ||
===== <span id="ypp" style="color:red">YPP</span>: Yaroslav [[Complexity Zoo:B#bpp|BPP]] ===== | ===== <span id="ypp" style="color:red">YPP</span>: Yaroslav [[Complexity Zoo:B#bpp|BPP]] ===== | ||
The probabilistic analogue of [[#yp|YP]]; it is to YP what [[Complexity Zoo:M#ma|MA]] is to [[Complexity Zoo:N#np|NP]]. Formally, the class of decision problems for which there exists a syntactic [[Complexity Zoo:B#bpp|BPP]] machine M such that: | The probabilistic analogue of [[#yp|YP]]; it is to YP what [[Complexity Zoo:M#ma|MA]] is to [[Complexity Zoo:N#np|NP]]. Formally, the class of decision problems for which there exists a syntactic [[Complexity Zoo:B#bpp|BPP]] machine M such that: | ||
| Line 38: | Line 44: | ||
Contains [[Complexity Zoo:B#bqp|BQP]] and [[#ypp|YPP]], and is contained in [[Complexity Zoo:Q#qma|QMA]] and [[Complexity Zoo:B#bqpqpoly|BQP/qpoly]]. | Contains [[Complexity Zoo:B#bqp|BQP]] and [[#ypp|YPP]], and is contained in [[Complexity Zoo:Q#qma|QMA]] and [[Complexity Zoo:B#bqpqpoly|BQP/qpoly]]. | ||
| + | ---- | ||
| + | |||
| + | ===== <span id="yqp*" style="color:red">YQP*</span>: Yaroslav [[Complexity Zoo:B#bqp|BQP]] star ===== | ||
| + | Is to [[#yqp|YQP]] as [[Complexity Zoo:Y#yp*|YP*]] is to [[Complexity Zoo:Y#yp|YP]] [[zooref#AD14|[AD14]]]. | ||
| + | |||
| + | ---- | ||
| + | ===== <span id="yqp*/poly" style="color:red">YQP*/poly</span>: [[Complexity Zoo:Y#yqp*|YQP*]] With Polynomial-Size Advice ===== | ||
| + | Equal to [[Complexity Zoo:B#bqpqpoly|BQP/qpoly]] [[zooref#AD14|[AD14]]]. | ||
| + | ---- | ||
Latest revision as of 10:20, 15 March 2024
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 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."
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.
YP*: Yaroslav-Percival Star
YP except the advice string s_n can be verified in polynomial time without needing the input x [AD14].
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 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."
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.
YQP*: Yaroslav BQP star
Is to YQP as YP* is to YP [AD14].