# 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(x
^{c}) such that A(x,y) = 1}

Algorithm A verifies

*L* in polynomial time.