Editing UP (complexity)

{{refimprove|date=August 2018}}
In [[computational complexity theory|complexity theory]], '''UP''' ('''unambiguous non-deterministic polynomial-time''') is the [[complexity class]] of [[decision problem]]s solvable in [[polynomial time]] on an [[unambiguous Turing machine]] with at most one accepting path for each input. '''UP''' contains '''[[P (complexity)|P]]''' and is contained in '''[[NP (complexity)|NP]]'''.

A common reformulation of '''NP''' states that a language is in '''NP''' if and only if a given answer can be verified by a deterministic machine in polynomial time. Similarly, a language is in '''UP''' if a given answer can be verified in polynomial time, and the verifier machine only accepts at most ''one'' answer for each problem instance. More formally, a language ''L'' belongs to '''UP''' if there exists a two-input polynomial-time algorithm ''A'' and a constant ''c'' such that 
:if x in ''L'' , then there exists a unique certificate ''y'' with <math>|y| = O(|x|^c)</math> such that {{tmath|1=A(x,y) = 1}}
:if x is not in ''L'', there is no certificate ''y'' with <math>|y| = O(|x|^c)</math> such that {{tmath|1=A(x,y) = 1}}
:algorithm ''A'' verifies ''L'' in polynomial time.

'''UP''' (and its [[complement (complexity)|complement]] '''co-UP''') contain both the [[integer factorization]] problem and [[parity game]] problem. Because determined effort has yet to find a polynomial-time solution to any of these problems, it is suspected to be difficult to show '''P'''='''UP''', or even '''P'''=('''UP''' ∩ '''co-UP''').

The [[Valiant–Vazirani theorem]] states that '''NP''' is contained in '''RP'''<sup>'''Promise-UP'''</sup>, which means that there is a randomized reduction from any problem in '''NP''' to a problem in '''[[promise problem|Promise-UP]]'''.

'''UP''' is not known to have any [[Complete (complexity)|complete]] problems.<ref>{{Cite web |title=U |url=https://complexityzoo.net/Complexity_Zoo:U#up |access-date= |website=[[Complexity Zoo]] |at=UP: Unambiguous Polynomial-Time}}</ref>

==References==
===Citations===
{{Reflist}}
===Sources===
*{{Cite journal |last=Hemaspaandra |first=Lane A. |last2=Rothe |first2=Jörg |date=June 1997 |title=Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets |url=http://epubs.siam.org/doi/10.1137/S0097539794261970 |journal=[[SIAM Journal on Computing]] |language=en |volume=26 |issue=3 |pages=634–653 |doi=10.1137/S0097539794261970 |issn=0097-5397|arxiv=cs/9907033 }}

{{ComplexityClasses}}

[[Category:Complexity classes]]