UP (complexity)

Quality 0.50 · 3 views · Updated 2 months ago

title: "UP (complexity)" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["complexity-classes"] topic_path: "general/complexity-classes" source: "https://en.wikipedia.org/wiki/UP_(complexity)" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

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. 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 :if x \not\in L, there is no certificate y with |y| = O(|x|^c) 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 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.

References

Citations

Sources

References

  1. (May 1976). "Relative complexity of checking and evaluating". [[Information Processing Letters]].
  2. "U".

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

complexity-classes