Skip to main content

UP (complexity)

UP (complexity)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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 such that
if x is not in L, there is no certificate y with 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 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.[1]

References[edit]

  1. ^ Complexity Zoo: UP

References[edit]

  • Lane A. Hemaspaandra and Jorg Rothe, Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets, SIAM J. Comput., 26(3) (June 1997), 634–653
Retrieved from "https://en.wikipedia.org/w/index.php?title=UP_(complexity)&oldid=951083651"

Comments

Post a Comment

Popular posts from this blog

Jacques Rancière

Image
Jacques Rancière From Wikipedia, the free encyclopedia   (Redirected from Jacques Ranciere ) Jump to navigation Jump to search French philosopher Jacques Rancière Born ( 1940-06-10 ) 10 June 1940 (age 81) Algiers , French Algeria (present-day Algiers, Algeria ) Nationality French Alma mater École Normale Supérieure Era 20th- / 21st-century philosophy Region Western philosophy School Continental philosophy Structural Marxism Institutions University of Paris VIII Main interests Political philosophy , aesthetics , philosophy of history , philosophy of education , cinema Notable ideas Theories of democracy, disagreement, the Visual, [1] "part of no part" [2] Influences Plato , Aristotle , Marx , Althusser , Foucault , Lacan , Lyotard , Badiou , Arendt , Lefort Influenced Laclau , Žižek , Critchley , Bernard Aspe , Kristin Ross , Todd May , Levi Bryant , Jodi Dean , Gabriel ...
Read more

Electronic keyboard

Image
Electronic keyboard From Wikipedia, the free encyclopedia Jump to navigation Jump to search Musical instrument "Portable keyboard" redirects here. For portable typing keyboards, see Wireless keyboard . This article needs additional citations for verification . Please help improve this article by adding citations to reliable sources . Unsourced material may be challenged and removed. Find sources:   "Electronic keyboard"  –  news   · newspapers   · books   · scholar   · JSTOR ( September 2020 ) ( Learn how and when to remove this template message ) Yamaha PSR-290 electronic keyboard A MIDI song played on a Casio electronic keyboard An electronic keyboard , portable keyboard , or digital keyboard is an electronic musical instrument , an electronic derivative of keyboard instruments . [1] Electronic keyboards include synthesizers , digital pianos , stage...
Read more

Wikipedia talk:WikiProject Countries/Proposal 1

Image
Wikipedia talk : WikiProject Countries/Proposal 1 From Wikipedia, the free encyclopedia < Wikipedia talk:WikiProject Countries Jump to navigation Jump to search This is a demonstration of some formatting ideas I had. Click here for the real Australia article. Australia is both the name of the world's smallest continent , and the short form of the Commonwealth of Australia . The Commonwealth of Australia is the sixth largest country in the world (geographically), the only one to occupy an entire continent, and the largest in Australasia . New Zealand is to to the southeast; Papua New Guinea , West Papua and Timor Leste to its north, and Indonesia northwest. The name 'Australia' comes from the Latin phrase terra australis incognita ("unknown southern land", see Terra Australis ). Commonwealth of Australia ( In Detail ) National motto : None Official language ...
Read more