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.
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 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.