- Source: 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 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
if x in L , then there exists a unique certificate y with
|
y
|
=
O
(
|
x
|
c
)
{\displaystyle |y|=O(|x|^{c})}
such that
A
(
x
,
y
)
=
1
{\displaystyle A(x,y)=1}
if x is not in L, there is no certificate y with
|
y
|
=
O
(
|
x
|
c
)
{\displaystyle |y|=O(|x|^{c})}
such that
A
(
x
,
y
)
=
1
{\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 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.
References
= Citations
== 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.
Kata Kunci Pencarian:
- Indonesia
- Globalisasi
- Rusia
- Stephen Cook
- Sosiologi komputasional
- Sub-Komisi Promosi dan Perlindungan Hak Asasi Manusia
- Kehidupan buatan
- Let's Encrypt
- Manusia
- Hokky Situngkir
- UP (complexity)
- Complexity
- Up
- Kolmogorov complexity
- Time complexity
- Cyclomatic complexity
- Computational complexity
- Computational complexity theory
- Communication complexity
- SL (complexity)
