Complexity Zoo:Y - Revision history

Yirkajk: /* YQP: Yaroslav BQP star / add result Contained in APP.

2024-07-07T15:41:12Z

YQP*: Yaroslav BQP star: add result Contained in APP.

AnAttemptAtProductivity at 10:20, 15 March 2024

2024-03-15T10:20:33Z

AnAttemptAtProductivity: Added complexity class YP*

2024-03-15T10:13:28Z

Added complexity class YP*

Quackack: /* YP: Your Polynomial-Time or Yaroslav-Percival */

2021-05-27T21:57:05Z

YP: Your Polynomial-Time or Yaroslav-Percival

Sniffnoy: /* YP: Your Polynomial-Time or Yaroslav-Percival */ update link

2013-07-11T22:49:20Z

YP: Your Polynomial-Time or Yaroslav-Percival: update link

Admin: 1 revision: Complexity zoo import.

2012-11-18T03:10:33Z

1 revision: Complexity zoo import.

New page

__NOTOC__
{{CZ-Letter-Menu|Y}}

===== 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:
<ul>
<li>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.</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>
Defined in a [http://www.blogger.com/comment.g?blogID=17392898&postID=114560148725169634 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]].

Also contains [[Complexity Zoo:P#p|P]] with [[Complexity Zoo:T#tally|TALLY]] ∩ [[Complexity Zoo:N#np|NP]] ∩ [[Complexity Zoo:C#conp|coNP]] oracle.

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

----

===== YPP: 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:
<ul>
<li>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.</li>
<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>
</ul>
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 [[Complexity Zoo:B#bpp|BPP]] and [[#yp|YP]], and is contained in [[Complexity Zoo:M#ma|MA]] and [[Complexity Zoo:P#ppoly|P/poly]].

----
===== YQP: Yaroslav [[Complexity Zoo:B#bqp|BQP]] =====
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 |ψ_n>.

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

@@ Line 48: / Line 48: @@
 ===== <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]]].
 ----

← Older revision		Revision as of 10:20, 15 March 2024
Line 44:		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]]].
		+	----

@@ Line 25: / Line 25: @@
 ----
 ===== <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:

← Older revision		Revision as of 21:57, 27 May 2021
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.

	----		----

@@ 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>
 </ul>
-Defined in a [http://www.blogger.com/comment.g?blogID=17392898&postID=114560148725169634 recent post] of the blog [http://www.scottaaronson.com/blog/ Shtetl-Optimized].  See there for an explanation of the class's name.
+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]].