Metraipolis › archive › dc_b89eacd29ff5

Unique games conjecture — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Unique_games_conjecture
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T16:14:19.892Z
SHA-256 of the archived text
1dddf15c451dc46ed7ebba79d96f71e1e00080bdd74d24197934e43ef9200a73
Stable URL of this page
https://metraipolis.com/documento/dc_b89eacd29ff5

How to cite

Unique games conjecture — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Unique_games_conjecture (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_b89eacd29ff5 (Metraipolis archive dc_b89eacd29ff5, sha256 1dddf15c451dc46ed7ebba79d96f71e1e00080bdd74d24197934e43ef9200a73)
BibTeX
@misc{dcb89eacd29ff5,
  title = {Unique games conjecture — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Unique_games_conjecture},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_b89eacd29ff5; sha256 1dddf15c451dc46ed7ebba79d96f71e1e00080bdd74d24197934e43ef9200a73},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Unique_games_conjecture. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in 2002, that it is NP-hard to approximate the value of a certain type of game, known as a unique game. It has broad applications in the theory of hardness of approximation. If the unique games conjecture is true and P ≠ NP, then for many important problems there not only does not exist an algorithm that always produces an exact solution in polynomial time (as postulated by the P versus NP problem), but even an algorithm that always produces a good approximation in polynomial time. The problems for which such an inapproximability result would hold include constraint satisfaction problems, which crop up in a wide variety of disciplines. According to Ryan O'Donnell as quoted by the Simons Foundation in 2012, academics were roughly evenly divided on whether the conjecture is true or false. In 2026, the OpenAI bulk release of mathematical papers included a paper that claimed to have proved the conjecture.

Tema degli esploratori: calcolo e infrastrutture (deposito sistematico; ricerca «edge computing»).
Fonte: Wikipedia in inglese, voce «Unique games conjecture» — https://en.wikipedia.org/wiki/Unique_games_conjecture
Wikidata Q7886950 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q7886950
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Unique_games_conjecture?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1380062359, consultata il 2026-10-15T15:41:18.548Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: ff34ef7727d9620c30bf6e16732b238d9069e2c46398c70c6aea6e7549edf9fc