UP (complexity)

Uses your system voice; voice and rate in settings.

Snapshot

≈ 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. 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 :if x \not\in L , there is no certificate y with |y| = O(|x|^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).…

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. 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 if x \not\in L , there is no certificate y with |y| = O(|x|^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 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

Text derived from https://en.wikipedia.org/w/index.php?oldid=1326582374 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001326582374 · captured 1765304660.0 · version history

Cite this page as: encyclopegia.org, “UP (complexity)”, snapshot enwiki-001326582374. https://encyclopegia.org/a/up-complexity

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.