# UP (complexity)

This article needs additional citations for verification. (August 2018) (Learn how and when to remove this template message) |

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 such that - if x is not in
*L*, there is no certificate*y*with such that - 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 **RP**^{Promise-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[edit]

## References[edit]

- Lane A. Hemaspaandra and Jorg Rothe,
*Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets*, SIAM J. Comput., 26(3) (June 1997), 634–653