UP (complexity): Difference between revisions
imported>OAbot m Open access bot: arxiv updated in citation with #oabot. |
No edit summary |
||
| Line 1: | Line 1: | ||
{{refimprove|date=August 2018}} | {{refimprove|date=August 2018}} | ||
In [[computational complexity theory|complexity theory]], '''UP''' ('''unambiguous non-deterministic polynomial-time''') is the [[complexity class]] of [[decision problem]]s solvable in [[polynomial time]] on an [[unambiguous Turing machine]] with at most one accepting path for each input. '''UP''' contains '''[[P (complexity)|P]]''' and is contained in '''[[NP (complexity)|NP]]'''. | In [[computational complexity theory|complexity theory]], '''UP''' ('''unambiguous non-deterministic polynomial-time''') is the [[complexity class]] of [[decision problem]]s 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 (complexity)|P]]''' and is contained in '''[[NP (complexity)|NP]]'''. | ||
A common reformulation of '''NP''' states that a language is in '''NP''' if and only if a given | 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.<ref>{{cite journal |last1=Valiant |first1=Leslie|authorlink = Leslie Valiant |title=Relative complexity of checking and evaluating |journal=[[Information Processing Letters]] |date=May 1976 |volume=5 |issue=1 |pages=20-23 |doi=10.1016/0020-0190(76)90097-1}}</ref> 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 | :if <math>x \in L</math>, then there exists a unique certificate ''y'' with <math>|y| = O(|x|^c)</math> such that {{tmath|1=A(x,y) = 1}} | ||
:if x | :if <math>x \not\in L</math>, there is no certificate ''y'' with <math>|y| = O(|x|^c)</math> such that {{tmath|1=A(x,y) = 1}} | ||
:algorithm ''A'' verifies ''L'' in polynomial time. | :algorithm ''A'' verifies ''L'' in polynomial time. | ||
Latest revision as of 19:24, 9 December 2025
Template:Refimprove 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 , then there exists a unique certificate y with such that Template:Tmath
- if , there is no certificate y with such that Template:Tmath
- 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
Citations
<templatestyles src="Reflist/styles.css" />
Script error: No such module "Check for unknown parameters".
Sources
- Script error: No such module "Citation/CS1".