### - Art Gallery -

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