UP (complexity)

In complexity theory, UP ("Unambiguous Non-deterministic Polynomial-time") is the complexity class of decision problems solvable in polynomial time on a 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})

such that

A(x,y)=1

if x is not in L, there is no certificate y with

|y|=O(|x|^{c})

such that

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 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.^[1]

References

↑ Complexity Zoo: UP

References

Lane A. HEMASPAANDRA and Jorg Rothe, Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets, SIAM J. Comput., 26(3), 634–653

Important complexity classes (more)

Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP APX

Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete

Considered infeasible	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL

Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy

Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

This article is issued from Wikipedia - version of the 8/20/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.