{
  "id": "enwiki-001326582374",
  "slug": "up-complexity",
  "title": "UP (complexity)",
  "qid": "",
  "lead": "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).…",
  "body": "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===",
  "categories": [
    "22984050",
    "23057298",
    "24043274"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1326582374",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1765304660.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001326582374",
    "type": "webpage",
    "title": "UP (complexity)",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/up-complexity",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001326582374",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1326582374",
    "note": "Immutable snapshot enwiki-001326582374"
  }
}