# P44: Unique Games conjecture

- ID: `P44`
- Reference: `unique-games-conjecture`
- Page: https://theoremdb.org/statements/P44
- Record maturity: Reviewed problem with recorded work

## 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\).

### Context

The conjecture would determine optimal approximation thresholds for many combinatorial optimization problems.

### Problem setup

- **Definition (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 (The optimum).** The optimum is the largest fraction of constraints simultaneously satisfied by an assignment.
- **Remark.** The conjecture would determine optimal approximation thresholds for many combinatorial optimization problems.

### What 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.

## Status

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](#reference-2) [1](#reference-1) [3](#reference-3)

## Work

### Evidence for the current status

**Claim 1 (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.

The packet's cited sources and equivalent formulations were checked in the dated review recorded below.

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.

### Background and intake notes

- Original intake status: 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.
- The gap formulation and status were checked against Khot's survey and current complexity references on 2026-07-22.
- The 2-to-2 games theorem proves a related weaker conjecture. Algorithms for restricted instances do not decide the general hardness claim.

### Open directions

- **Route 1** (reported): 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. [1](#reference-1)

### Computational notes

- Benchmark performance on finite instances cannot prove or refute an asymptotic NP-hardness statement.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `unique-games-conjecture`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Subhash Khot, On the Unique Games Conjecture, survey. cs.nyu.edu checked 2026-08-01. Subhash Khot, survey, statement and overview of the conjecture https://cs.nyu.edu/~khot/papers/UGCSurvey.pdf
   - Also cited at Conjecture statement and overview
   - Also cited at Editorial research route recorded 2026-07-31
   - website; primary source; Author survey manuscript checked 2026-08-01; checked 2026-07-31
   - Source 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.
   - 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.
2. <a id="reference-2"></a>Amey Bhangale and Subhash Khot, UG-hardness to NP-hardness by Losing Half, Theory of Computing 18 (2022), Article 5. Abstract and introduction https://theoryofcomputing.org/articles/v018a005/
   - journal_article; primary source; checked 2026-08-01
   - Source use: original_summary
   - States UGC is open and records the 2-to-2 theorem's consequence.
3. <a id="reference-3"></a>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 https://theoryofcomputing.org/articles/v021a011/
   - journal_article; primary source; checked 2026-08-01
   - Source use: original_summary
   - Current conditional route and explicit non-consensus status.