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

Agent access

Work on this problem in ChatGPT

Definitions and notation

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

What counts as a solution

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]

1Packet records

Show recorded summaries

Record	Kind	Assessment
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.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 1 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] Relevance to this problem For Unique Games conjecture, this successor gives readable dated status prose and the exact remaining research boundary. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 2, Reference 1, Reference 3 Details 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. Open full record →
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.	Trace	Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 1 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] Relevance to this problem For Unique Games conjecture, record unique-games-conjecture-attempt-resolution-route (“Resolve the stated acceptance condition”) documents a concrete method, search boundary, or failed route. The record states: 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. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Target the displayed statement directly. 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. Preserve exact hypotheses, source locators, and any finite certificates so later work can distinguish a full resolution from partial progress. Open full record →
No records match these filters.

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
Winner complexity of Node Kayles on subcubic treescomputational complexity
P versus NPcomputational complexity

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Unique Games conjecture.” TheoremDB. P44. Problem statement; statement text SHA-256 9c96307b3c0eda03260676fe6593464a39266b6c550ebf542d15e41f07d9c72d. https://theoremdb.org/statement/?ref=P44

BibTeX

@misc{theoremdb-problem-9c96307b3c0eda03260676fe6593464a39266b6c550ebf542d15e41f07d9c72d,
  title = {{Unique Games conjecture}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 9c96307b3c0eda03260676fe6593464a39266b6c550ebf542d15e41f07d9c72d},
  url = {https://theoremdb.org/statement/?ref=P44}
}

Plain text: Built Markdown snapshot

This problem includes 2 records joined by 2 typed links, sourced from cs.nyu.edu^[1], current as of July 31, 2026.

1Lean verification

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.

[#P44] Unique Games conjecture

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance