Difference between revisions of "Complexity Zoo:Y"

From Complexity Zoo
Jump to navigation Jump to search
(Added complexity class YP*)
Line 25: Line 25:
 
----
 
----
  
 +
===== <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:

Revision as of 10:13, 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 - YP - YPP - YQP


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