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