In complexity theory, UP (unambiguous non-deterministic polynomial-time) is the

complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of ...

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

s solvable in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

on an

unambiguous Turing machine In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers. An unambiguous Turing machine is a special kind of non-deterministic Turing machi ...

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 :if x is not in ''L'', there is no certificate ''y'' with

, y,  = O(, x, ^c)

such that :algorithm ''A'' verifies ''L'' in polynomial time. UP (and its

complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class ...

co-UP) contain both the

integer factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are suf ...

problem and

parity game A parity game is played on a colored directed graph, where each node has been colored by a priority – one of (usually) finitely many natural numbers. Two players, 0 and 1, move a (single, shared) token along the edges of the graph. The owne ...

problem; because determined effort has yet to find a polynomial-time solution to any of these problems, it is suspected to be difficult to show P=UP, or even P=(UP ∩ co-UP). The

Valiant–Vazirani theorem The Valiant–Vazirani theorem is a theorem in computational complexity theory stating that if there is a polynomial time algorithm for Unambiguous-SAT, then NP = RP. It was proven by Leslie Valiant and Vijay Vazirani in their paper ...

states that NP is contained in RP^Promise-UP, which means that there is a randomized reduction from any problem in NP to a problem in Promise-UP. UP is not known to have any

complete Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies t ...

problems.

References

*Lane A. Hemaspaandra and Jorg Rothe, ''Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets'', SIAM J. Comput., 26(3) (June 1997), 634–653 {{ComplexityClasses Complexity classes