The UP (complexity) reference article from the English Wikipedia on 24-Apr-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

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.

Important Complexity classes

P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | NC | P-C

PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP

This is the "UP (complexity)" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.