UP (complexity)

In complexity theory, UP (unambiguous non-deterministic polynomial-time) is the complexity class of decision problems solvable in polynomial time on an unambiguous Turing machine (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 "certificate" can be verified by a deterministic machine in polynomial time. Similarly, a language is in UP if a given certificate can be verified in polynomial time, and the verifier machine only accepts at most one certificate for each problem instance. ^[1] 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 ${\displaystyle x\in L}$, then there exists a unique certificate y with ${\displaystyle |y|=O(|x|^{c})}$ such that ⁠${\displaystyle A(x,y)=1}$⁠

if ${\displaystyle x\not \in L}$, there is no certificate y with ${\displaystyle |y|=O(|x|^{c})}$ such that ⁠${\displaystyle A(x,y)=1}$⁠

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 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. ^[2]

References

Citations

1. Valiant, Leslie (May 1976). "Relative complexity of checking and evaluating". Information Processing Letters . 5 (1): 20–23. doi:10.1016/0020-0190(76)90097-1.
2. "U". Complexity Zoo . UP: Unambiguous Polynomial-Time.

Sources

• Hemaspaandra, Lane A.; Rothe, Jörg (June 1997). "Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets". SIAM Journal on Computing . 26 (3): 634–653. arXiv: cs/9907033 . doi:10.1137/S0097539794261970. ISSN   0097-5397.