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.
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(xc) such that A(x,y) = 1}
Algorithm A verifies
L in polynomial time.