UP (complexity)
Encyclopedia
In complexity theory
, UP ("Unambiguous Non-deterministic Polynomial-time") is the complexity class
of decision problem
s 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
.
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
Algorithm A verifies L in polynomial time.
UP (and its complement
co-UP) contain both the integer factorization
problem and parity game
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 RPPromise-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.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, UP ("Unambiguous Non-deterministic Polynomial-time") is the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
of decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s solvable in polynomial time on a non-deterministic Turing machine
Non-deterministic 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....
with at most one accepting path for each input. UP contains P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
and is contained in NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
.
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
Complement (complexity)
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is its complement...
co-UP) contain both the integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
problem and parity game
Parity game
A parity game is played on a colored directed graph, where each node has been colored by a priority – one of finitely many natural numbers. Two players, 0 and 1, take turns moving a token along the edges of the graph, resulting in a path, called the play.The winner of a finite play is the...
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
Valiant-Vazirani theorem
The Valiant–Vazirani theorem is a theorem in computational complexity theory. It was proven by Leslie Valiant and Vijay Vazirani in their paper titled "NP is as easy as detecting unique solutions" published in 1986...
states that NP is contained in RPPromise-UP, which means that there is a randomized reduction from any problem in NP to a problem in Promise-UP
Promise problem
In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a subset of all possible inputs. Unlike decision problems, the yes instances and no instances do not exhaust the set of all inputs...
.
UP is not known to have any complete problems.