[#P44] Unique Games conjecture
Problem. For every \(\varepsilon,\delta>0\), there exists an alphabet size \(q\) such that it is NP-hard to distinguish unique games with optimum at least \(1-\varepsilon\) from those with optimum at most \(\delta\).
1Context
The conjecture would determine optimal approximation thresholds for many combinatorial optimization problems.
2Problem setup
Definition 1 (A unique game). A unique game is a constraint-satisfaction problem in which every constraint between two variables is a permutation matching of their alphabet values.
Definition 2 (The optimum). The optimum is the largest fraction of constraints simultaneously satisfied by an assignment.
Remark 1. The conjecture would determine optimal approximation thresholds for many combinatorial optimization problems.
3What counts as a solution
- Prove the stated NP-hardness for every epsilon under standard polynomial-time reductions, or give a polynomial-time algorithm or complexity-theoretic argument that refutes the asserted gap hardness.
1Status
Current status (Dated status and exact unresolved remainder). Unresolved in this packet after the dated source check. Strongest checked result: The 2-to-2 Games Theorem gives NP-hardness at completeness about 1/2 and arbitrarily small soundness. A 2025 route toward 2-to-1 Games remains conditional. Exact unresolved remainder: Prove the near-1 versus near-0 NP-hardness gap for every epsilon, or refute it by an algorithm or complexity argument.[2][1][3]
1Records
Notes and companion material
Original intake status. The cited survey presents the Unique Games conjecture as unresolved, and current public status was checked on 2026-07-31. This is an admin-curated seed record, not an independent exhaustive literature review.
- The 2-to-2 games theorem proves a related weaker conjecture. Algorithms for restricted instances do not decide the general hardness claim.
Computational notes
- Benchmark performance on finite instances cannot prove or refute an asymptotic NP-hardness statement.
2See also
- Complexity of equality for binary-code weight enumeratorscomputational complexity
- Quantum PCP conjecturecomputational complexity
- P versus NPcomputational complexity
How to cite
TheoremDB contributors, “Unique Games conjecture,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/unique-games-conjectureThis page as plain text: unique-games-conjecture.md
This problem includes 2 records joined by 2 typed links, sourced from cs.nyu.edu[1], current as of July 31, 2026.
1References
- Packet source. Subhash Khot, On the Unique Games Conjecture, survey. cs.nyu.edu checked 2026-08-01. Subhash Khot, survey, statement and overview of the conjecture. ↗website · primary source · Author survey manuscript checked 2026-08-01 · checked 2026-07-31Source use: original summary.The cited survey presents the Unique Games conjecture as unresolved, and current public status was checked on 2026-07-22. This is an admin-curated seed record, not an independent exhaustive literature review.Also cited at Conjecture statement and overview.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.Packet-linked formulation.Source named by the research packet.
- Amey Bhangale and Subhash Khot, UG-hardness to NP-hardness by Losing Half, Theory of Computing 18 (2022), Article 5. Abstract and introduction. ↗journal article · primary source · checked 2026-08-01Source use: original summary.States UGC is open and records the 2-to-2 theorem's consequence.
- Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra, Towards a Proof of the 2-to-1 Games Conjecture, Theory of Computing 21 (2025), Article 11. Abstract and introduction. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Current conditional route and explicit non-consensus status.
An original CC0 restatement prepared by TheoremDB maintainers.