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 (a nondeterministic Turing machine with at most one…

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 x∈L, then there exists a unique certificate y with |y|=O(|x|c) such that ⁠A(x,y)=1⁠
if x∉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 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

edit edit source

Citations

edit edit source
  1. ^ Valiant, Leslie (May 1976). "Relative complexity of checking and evaluating". Information Processing Letters. 5 (1): 20–23. doi:10.1016/0020-0190(76)90097-1. Wikipedia revision 1326582374, retrieved 2026-11-19
  2. ^ "U". Complexity Zoo. UP: Unambiguous Polynomial-Time. Wikipedia revision 1326582374, retrieved 2026-11-19

Sources

edit edit source Complexity classesConsidered feasible Suspected infeasible Considered infeasible Other complexity classes Class hierarchies Families of classes List of complexity classes

Text derived from https://en.wikipedia.org/w/index.php?oldid=1326582374 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001326582374 · captured 2025-12-09 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “UP (complexity)”, snapshot enwiki-001326582374. https://encyclopegia.org/a/up-complexity