UP (complexity)

In complexity theory, UP ("Unambiguous Non-deterministic Polynomial-time") is the complexity class of decision problems solvable in polynomial time on a non-deterministic Turing machine with at most one accepting path for each input. UP contains P and is contained in NP. If P ≠ NP then either P ≠ UP or UP ≠ NP or both must be true.

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 :L = {x in {0,1}* | ∃! certificate, y with |y| = O(|x|^c) such that A(x,y) = 1}Algorithm A verifies "L" in polynomial time.

UP (and its complement co-UP) contain the integer factorization problem; because determined effort has yet to find a polynomial-time solution to this problem, it is suspected to be difficult to show P=UP, or even P=UP ∩ co-UP.