https://complexityzoo.net/api.php?action=feedcontributions&user=Sniffnoy&feedformat=atomComplexity Zoo - User contributions [en]2024-03-28T18:29:20ZUser contributionsMediaWiki 1.35.0https://complexityzoo.net/index.php?title=Complexity_Zoo:Y&diff=6249Complexity Zoo:Y2013-07-11T22:49:20Z<p>Sniffnoy: /* YP: Your Polynomial-Time or Yaroslav-Percival */ update link</p>
<hr />
<div>__NOTOC__<br />
{{CZ-Letter-Menu|Y}}<br />
<br />
<br />
===== <span id="yacc" style="color:red">YACC</span>: Yet Another Complexity Class =====<br />
A term of derision, used against a complexity class.<br />
<br />
----<br />
===== <span id="yp" style="color:red">YP</span>: Your Polynomial-Time or Yaroslav-Percival =====<br />
The class of decision problems for which there exists a polynomial-time machine M such that:<br />
<ul><br />
<li>For all input sizes n, there exists a polynomial-size advice string s<sub>n</sub> such that M(x,s<sub>n</sub>) outputs the correct answer for all inputs x of size n.</li><br />
<li>For all inputs x and advice strings s, M(x,s) outputs either the correct answer or "I don't know."</li><br />
</ul><br />
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.<br />
<br />
Contains [[Complexity Zoo:Z#zpp|ZPP]] by the same argument that places [[Complexity Zoo:B#bpp|BPP]] in [[Complexity Zoo:P#ppoly|P/poly]].<br />
<br />
Also contains [[Complexity Zoo:P#p|P]] with [[Complexity Zoo:T#tally|TALLY]] &#8745; [[Complexity Zoo:N#np|NP]] &#8745; [[Complexity Zoo:C#conp|coNP]] oracle.<br />
<br />
Is contained in [[Complexity Zoo:N#npiconp|NP &#8745; coNP]] and [[#ypp|YPP]].<br />
<br />
----<br />
<br />
===== <span id="ypp" style="color:red">YPP</span>: Yaroslav [[Complexity Zoo:B#bpp|BPP]] =====<br />
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:<br />
<ul><br />
<li>For all input sizes n, there exists a polynomial-size advice string a<sub>n</sub> such that for all inputs x of size n, M(x,a<sub>n</sub>) outputs the correct answer with probability at least 2/3.</li><br />
<li>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.</li><br />
</ul><br />
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."<br />
<br />
Contains [[Complexity Zoo:B#bpp|BPP]] and [[#yp|YP]], and is contained in [[Complexity Zoo:M#ma|MA]] and [[Complexity Zoo:P#ppoly|P/poly]].<br />
<br />
----<br />
===== <span id="yqp" style="color:red">YQP</span>: Yaroslav [[Complexity Zoo:B#bqp|BQP]] =====<br />
Is to [[#ypp|YPP]] as [[Complexity Zoo:B#bqp|BQP]] is to [[Complexity Zoo:B#bpp|BPP]], and [[Complexity Zoo:Q#qma|QMA]] is to [[Complexity Zoo:M#ma|MA]]. The machine is now a quantum computer and the advice is a quantum state |&psi;_n&gt;.<br />
<br />
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]].</div>Sniffnoy