In
complexity theory, UP (unambiguous non-deterministic polynomial-time) is the
complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems of related resource-based computational complexity, complexity. The two most commonly analyzed resources are time complexity, time and spa ...
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 wheth ...
s solvable in
polynomial time on an
unambiguous 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
such that
:if x is not in ''L'', there is no certificate ''y'' with
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-clas ...
co-UP) contain both the
integer factorization 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 own ...
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 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 problems.
References
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