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 s ...
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 on a set of input values. An example of a decision problem is deciding whether a given natura ...
s solvable in
polynomial time
In theoretical 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 p ...
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 co-UP) contain both the
integer factorization
In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is a comp ...
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 ow ...
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 problems.
References
Citations
Sources
*
{{ComplexityClasses
Complexity classes