UP complexity

In complexity theory, UP ("Unambiguous Non-deterministic Polynomial-time") is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine where there exists exactly one accepting path if the string is accepted. This is a subset (though not necessarily proper) of NP and a superset (though not necessarily proper) of P. However, it is likely that either P ≠ UP or UP ≠ NP, since otherwise P = NP, which is widely believed to be false.

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.

This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia article. Browse Wikipedia for more information.