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…
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 x∈L, then there exists a unique certificate y with |y|=O(|x|c) such that A(x,y)=1
- if x∉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 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.[2]
References
edit edit sourceCitations
edit edit source- ^ 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. Wikipedia revision 1326582374, retrieved 2026-11-19
- ^ "U". Complexity Zoo. UP: Unambiguous Polynomial-Time. Wikipedia revision 1326582374, retrieved 2026-11-19
Sources
edit edit source- 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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1326582374 under CC BY-SA 4.0; modifications have been made.