Matches in DBpedia 2014 for { <http://dbpedia.org/resource/UP_(complexity)> ?p ?o. }
Showing items 1 to 25 of
25
with 100 items per page.
- UP_(complexity) abstract "In complexity theory, UP ("Unambiguous Non-deterministic Polynomial-time") is the complexity class of decision problems solvable in polynomial time on a non-deterministic 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) such that A(x,y) = 1if x isn't in L, there is no certificate y with |y| = O(|x|c) such that A(x,y) = 1Algorithm 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.".
- UP_(complexity) wikiPageID "312240".
- UP_(complexity) wikiPageRevisionID "541208990".
- UP_(complexity) hasPhotoCollection UP_(complexity).
- UP_(complexity) subject Category:Complexity_classes.
- UP_(complexity) type Abstraction100002137.
- UP_(complexity) type Class107997703.
- UP_(complexity) type Collection107951464.
- UP_(complexity) type ComplexityClasses.
- UP_(complexity) type Group100031264.
- UP_(complexity) comment "In complexity theory, UP ("Unambiguous Non-deterministic Polynomial-time") is the complexity class of decision problems solvable in polynomial time on a non-deterministic 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.".
- UP_(complexity) label "UP (clase de complejidad)".
- UP_(complexity) label "UP (complexity)".
- UP_(complexity) label "UP (複雜度)".
- UP_(complexity) label "UP (計算複雑性理論)".
- UP_(complexity) label "يو بي (تعقيد حسابي)".
- UP_(complexity) sameAs UP_(clase_de_complejidad).
- UP_(complexity) sameAs UP_(計算複雑性理論).
- UP_(complexity) sameAs UP_(복잡도).
- UP_(complexity) sameAs m.01tbb9.
- UP_(complexity) sameAs Q906584.
- UP_(complexity) sameAs Q906584.
- UP_(complexity) sameAs UP_(complexity).
- UP_(complexity) wasDerivedFrom UP_(complexity)?oldid=541208990.
- UP_(complexity) isPrimaryTopicOf UP_(complexity).