In complexity theory, UP (unambiguous non-deterministic polynomial-time) is the complexity class of decision problems solvable in polynomial time on an unambiguous Turing machine with at most one accepting path for each input. UP contains P and is contained in 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\( {\displaystyle |y|=O(|x|^{c})} \) such that \( {\displaystyle A(x,y)=1} \)
if x is not in L, there is no certificate y with \( {\displaystyle |y|=O(|x|^{c})} \) such that \( {\displaystyle A(x,y)=1} \)
algorithm A verifies L in polynomial time.
UP (and its 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 RPPromise-UP, which means that there is a randomized reduction from any problem in NP to a problem in Promise-UP.
UP is not known to have any complete problems.[1]
References
Complexity Zoo: UP
References
Lane A. Hemaspaandra and Jorg Rothe, Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets, SIAM J. Comput., 26(3) (June 1997), 634–653
vte
Important complexity classes (more)
Considered feasible
DLOGTIME AC0 ACC0 TC0 L SL RL NL NC SC CC P
P-complete ZPP RP BPP BQP APX
Suspected infeasible
UP NP
NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P
#P-complete IP PSPACE
PSPACE-complete
Considered infeasible
EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies
Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes
DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
