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. It is likely that either P ≠ UP or UP ≠ NP, since otherwise P = NP, which is widely believed to be false. Most believe that both inequalities hold.

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.

Papadimitriou discusses UP in the context of cryptography, where it is shown that UP=P if and only if a particular kind of one-way function does not exist. 1 Since UP lies between P and NP, this implies that finding a one-way function would suffice to show PNP.

Footnotes

1. Papadimitriou, section 12.1, subsection Cryptography and complexity, pg.283.

 Important complexity classes (more) P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | L | NC | P-C PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy