UP (complexity)
In complexity theory, UP ("Unambiguous Nondeterministic Polynomialtime") is the complexity class of decision problems solvable in polynomial time on a nondeterministic Turing machine with at most one accepting path for each input. UP contains P and is contained in NP.
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
 if x in L , then there exists a unique certificate y with y = O(x^{c}) such that A(x,y) = 1
 if x isn't in L, there is no certificate y with y = O(x^{c}) such that A(x,y) = 1
Algorithm A verifies L in polynomial time.
UP (and its complement coUP) contain both the integer factorization problem and parity game problem; because determined effort has yet to find a polynomialtime solution to any of these problems, it is suspected to be difficult to show P=UP, or even P=(UP ∩ coUP).
The ValiantVazirani theorem states that NP is contained in RP^{PromiseUP}, which means that there is a randomized reduction from any problem in NP to a problem in PromiseUP.
UP is not known to have any complete problems.^{1}
References

HPTS  Area Progetti  EduSoft  JavaEdu  N.Saperi  Ass.Scuola..  TS BCTV  TS VideoRes  TSODP  TRTWE  