we-solve (beta)

CS-18 · computer science · mathematics · Computational complexity

The Unique Games Conjecture

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

For $[k]=\{1,\ldots,k\}$, a unique game has a nonempty finite edge set and a permutation $\pi_e$ of $[k]$ on each directed edge $e=(v,w)$. Its optimum is \[ \operatorname{val}(G)=\max_{L:V\to[k]}\frac{\#\{e=(v,w):\pi_e(L(v))=L(w)\}}{|E|}. \] For every fixed $\varepsilon,\delta>0$ with $\varepsilon+\delta<1$, some fixed $k$ makes distinguishing $\operatorname{val}(G)\ge1-\varepsilon$ from $\operatorname{val}(G)\le\delta$ NP-hard under deterministic polynomial-time many-one reductions. Intermediate values lie outside the promise. The alphabet size depends on the accuracy parameters, not on the growing input graph.

Formulation and concept references: [S1].

Short English statement

Is it computationally intractable to distinguish almost satisfiable permutation constraints from ones where almost none can be satisfied?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 6

CS-18-A6 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on CS-18

Unique Games Conjecture

Definitions and mathematical statement

Shared notation.
Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

A Unique Games instance assigns labels from a finite alphabet to graph vertices, with each edge imposing a permutation relation on the endpoint labels. Its value is the largest fraction of satisfiable edges. The standard conjecture asks whether, for every positive tolerance, a sufficiently large alphabet makes distinguishing near-unit value from near-zero value NP-hard.

Record scope and qualifications.
The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. This repeats the Unique Games target already represented by canonical source records 43 and 30001374.

Source-record limitation: Duplicate Unique Games target, already present under IDs 43 and 30001374.

Related catalogue records: 43, 30001374. Separate source IDs are preserved for their provenance.

Statement recorded in the supplied source.
For every $\varepsilon>0$, does there exist an alphabet size $k$ such that it is NP-hard to distinguish Unique-Games instances of value at least $1-\varepsilon$ from instances of value at most $\varepsilon$? [S2]
Source status.
The supplied catalogue labels this source record open; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Ask whether nearly satisfiable permutation-constraint instances are hard to distinguish from ones with very low satisfiable value.

Sources

Preparation and review.
The original source and UnsolvedMath contributors retain attribution for the source extract. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, scope notes and formatting. No new human mathematical authorship or independently verified solution is asserted. Permanent source ID 30004014 and code OWR-16634-007 checked against the complete supplied registry and current repository. Distinct upstream records, including repeated questions and broad or damaged extracts, are retained for complete coverage of the source CS category. A repeated record is not a new independent conjecture. Complete mathematical-equivalence and current-literature review has not been performed. Related canonical identities: 43, 30001374. Preparation and final review follow contribution prompts C and D, with source gaps disclosed. Structural and rendering checks do not establish a new theorem or open status.

Research attempt

Literature, source context and scope

The full original catalogue body and source qualifications are preserved above. The relevant primary workshop passages were read in the cached publisher report. Historical claims and subsequent attributed results are distinguished from the mathematical work below. A restricted example, standard lemma or known theorem is not counted as new progress on the entire original target. Missing assumptions and repeated or rhetorical extracts are not silently turned into different solved problems.

The basic pairwise marginal relaxation cannot distinguish any instance

This is a repeated Unique Games target; its identity and provenance are retained. We test the basic local-marginal linear relaxation. For a label alphabet of size $k\ge1$, use vertex probabilities $p_v(a)$ and edge joint probabilities $q_{uv}(a,b)$, nonnegative and normalized, with each edge's marginals equal to the endpoint probabilities. Maximize the average probability that an edge permutation constraint is satisfied.
Proposition: For every nonempty-edge Unique Games instance, this relaxation has optimum 1, even when no satisfying labeling exists.
Proof: Set $p_v(a)=1/k$ for every vertex and label. For each oriented constraint $b=\pi_{uv}(a)$, put $q_{uv}(a,b)=1/k$ on its $k$ allowed pairs and zero otherwise. Because $\pi_{uv}$ is a permutation, both marginals are uniform, so the assignment is feasible. Each edge is satisfied with probability 1 in its own local table; hence the relaxation attains 1, which is also the largest possible average probability. For a concrete integrality gap, take a triangle with two identity constraints on the binary alphabet and one flip constraint. The two identity edges would force all three labels equal, contradicting the flip, so no labeling satisfies all three. A constant labeling satisfies two edges, giving true value exactly $2/3$, while the marginal relaxation remains 1. ∎
The local tables cannot be combined into one global joint distribution supported on satisfying labelings in this example. Thus checking pairwise consistency is the exact failed inference. Stronger semidefinite or higher-order relaxations add information absent here, so this does not establish a barrier for all algorithms or settle the conjectured hardness gap.

Verification and remaining gaps

All eight triangle labelings and all local marginal sums were checked exactly; the values are $2/3$ and 1 as stated. The primary report discusses later progress on related label-cover gaps, but this attempt proves no new complexity reduction. It leaves the quantified near-unit versus near-zero promise unresolved and does not count a repeated record as a new independent conjecture.

References and source attribution

Primary workshop report: https://doi.org/10.4171/owr/2018/51. Relevant passages read: 2018/51 pp. 3052--3053, Unique Games conjecture, exact satisfiability qualification and related label-cover progress.

All retrievals were checked on 11 October 2026. Original question attribution remains in the preserved Sources section. External theorems are attributed and not claimed as new discoveries or fully verified merely by citation.

Integration review.
Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% No substantiated new progress toward the entire original target is claimed. The worked results and failed route are delimited above; a known result, illustrative model, or auxiliary obstruction is not counted as original-target completion.

Final status and attribution

Attempt status: unresolved. This describes this research attempt, not a new ruling on the source catalogue's status or on external literature claims. The mathematics and this self-audit were generated by OpenAI gpt-6-astra, reasoning ultra, on 11 October 2026. Codex (GPT-6; exact serving revision not exposed) orchestrated the batch, reviewed the written mathematical arguments, and contributed formatting/repository review. This additional model review is not independent human verification. No human mathematical authorship, independent human proof checking, or formal verification is claimed. The historical preparation paragraphs in the reproduced catalogue body concern that body only.

Contribution prompt A was applied to the complete definition and supplied source record, followed by the adversarial checks of prompt B. Local reproduction files are batch022/checks.py, computations.json, and the per-ID audit JSON. They were not public links at preparation time. Numerical checks are finite and do not prove unrestricted results. No LaTeX engine was found locally; compilation was not performed by this research agent.

Go to contribution →

CS-18-A5 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on CS-18

Unique Games Conjecture

Definitions and mathematical statement

Shared notation.
Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

A Unique Games instance assigns labels from a finite alphabet to graph vertices, with each edge imposing a permutation relation on the endpoint labels. Its value is the largest fraction of satisfiable edges. The standard conjecture asks whether, for every positive tolerance, a sufficiently large alphabet makes distinguishing near-unit value from near-zero value NP-hard.

Record scope and qualifications.
The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. This repeats the Unique Games target already represented by canonical source records 43 and 30001374.

Source-record limitation: Duplicate Unique Games target, already present under IDs 43 and 30001374.

Related catalogue records: 43, 30001374. Separate source IDs are preserved for their provenance.

Statement recorded in the supplied source.
Is Khot's Unique Games Conjecture true? [S2]
Source status.
The supplied catalogue labels this source record open; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Ask whether nearly satisfiable permutation-constraint instances are hard to distinguish from ones with very low satisfiable value.

Sources

Preparation and review.
The original source and UnsolvedMath contributors retain attribution for the source extract. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, scope notes and formatting. No new human mathematical authorship or independently verified solution is asserted. Permanent source ID 30002240 and code OWR-12177-009 checked against the complete supplied registry and current repository. Distinct upstream records, including repeated questions and broad or damaged extracts, are retained for complete coverage of the source CS category. A repeated record is not a new independent conjecture. Complete mathematical-equivalence and current-literature review has not been performed. Related canonical identities: 43, 30001374. Preparation and final review follow contribution prompts C and D, with source gaps disclosed. Structural and rendering checks do not establish a new theorem or open status.

Research attempt

Literature, source context and scope

The full original catalogue body and source qualifications are preserved above. The relevant primary workshop passages were read in the cached publisher report. Historical claims and subsequent attributed results are distinguished from the mathematical work below. A restricted example, standard lemma or known theorem is not counted as new progress on the entire original target. Missing assumptions and repeated or rhetorical extracts are not silently turned into different solved problems.

Exact consistency does not solve the near-perfect gap

The source surveys the Unique Games Conjecture and semidefinite approaches. We test an elementary propagation route. Consider a finite graph with alphabet $[q]$, $q\ge1$, and each oriented edge $uv$ carrying a permutation $\pi_{uv}$, with the reverse constraint its inverse. A labeling satisfies this edge when $\ell(v)=\pi_{uv}(\ell(u))$.
Proposition: Whether all edges can be satisfied is decidable in $O(q(|V|+|E|))$ permutation evaluations. However, this exact test rejects instances whose optimum satisfied fraction tends to one.
Proof: In each connected component choose a root and a spanning tree. For every possible root label, propagate labels along tree edges using their permutations or inverses, then check every edge. Every fully satisfying labeling is uniquely determined by its root label along that tree, so the procedure succeeds exactly when a fully satisfying labeling exists. The claimed cost follows by trying $q$ labels in each component and summing their sizes. For the second assertion take a cycle of length $L\ge3$ with alphabet $\{0,1\}$. Give $L-1$ edges identity constraints and the remaining edge the flip $b\mapsto1-b$. Satisfying all edges would propagate a label around the cycle to its complement, an impossibility. The constant-zero labeling satisfies all identity edges, so the optimum is exactly $(L-1)/L$. ∎
The attempted inference "efficient exact consistency testing refutes the conjecture" therefore fails. For every fixed $\eta>0$, a cycle with $L>1/\eta$ is a near-perfect instance, yet the exact test rejects it. A promise distinction between value at least $1-\eta$ and value at most a small constant is a different task; the cycle example alone gives neither an algorithm nor a hardness proof for that distinction.

Verification and remaining gaps

All binary labelings of the frustrated cycles with $3\le L\le10$ were enumerated, obtaining optimum $L-1$ satisfied edges. The propagation algorithm was also checked against exhaustive satisfiability for these examples. No new gap algorithm, semidefinite hierarchy analysis, or complexity lower bound is established. The 2012 survey's historical algorithmic claims are not presented as current exhaustive knowledge.

References and source attribution

Primary workshop report: https://doi.org/10.4171/owr/2012/54. Relevant passages read: 2012/54 p. 3286, Boaz Barak’s survey of Unique Games, subexponential algorithms and sum-of-squares candidates.

All retrievals were checked on 11 October 2026. Original question attribution remains in the preserved Sources section. External theorems are attributed and not claimed as new discoveries or fully verified merely by citation.

Integration review.
Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% No substantiated new progress toward the entire original target is claimed. The worked results and failed route are delimited above; a known result, illustrative model, or auxiliary obstruction is not counted as original-target completion.

Final status and attribution

Attempt status: unresolved. This describes this research attempt, not a new ruling on the source catalogue's status or on external literature claims. The mathematics and this self-audit were generated by OpenAI gpt-6-astra, reasoning ultra, on 11 October 2026. Codex (GPT-6; exact serving revision not exposed) orchestrated the batch, reviewed the written mathematical arguments, and contributed formatting/repository review. No human mathematical authorship, independent human proof checking, or formal verification is claimed. The historical preparation paragraphs in the reproduced catalogue body concern that body only.

Contribution prompt A was applied to the complete definition and supplied source record, followed by the adversarial checks of prompt B. Local reproduction files are batch019/checks.py, computations.json, and the per-ID audit JSON. They were not public links at preparation time. Numerical checks are finite and do not prove unrestricted results. No LaTeX engine was found locally; compilation was not performed by this research agent.

Go to contribution →

CS-18-A4 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on CS-18

Research-attempt provenance

Definitions and mathematical statement

Shared notation.
Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

A Unique Games instance assigns labels from a finite alphabet to graph vertices, with each edge imposing a permutation relation on the endpoint labels. Its value is the largest fraction of satisfiable edges. The standard conjecture asks whether, for every positive tolerance, a sufficiently large alphabet makes distinguishing near-unit value from near-zero value NP-hard.

Record scope and qualifications.
The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. This repeats the Unique Games target already represented by canonical source records 43 and 30001374.

Source-record limitation: Duplicate Unique Games target, already present under IDs 43 and 30001374.

Related catalogue records: 43, 30001374. Separate source IDs are preserved for their provenance.

Statement recorded in the supplied source.
Is the Unique Games constraint-satisfaction problem computationally hard as asserted by the Unique Games Conjecture? [S2]
Source status.
The supplied catalogue labels this source record open; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Ask whether nearly satisfiable permutation-constraint instances are hard to distinguish from ones with very low satisfiable value.

Sources

  • S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30001938 (OWR-11451-013). Catalogue curation and metadata: CC BY 4.0. The source extract is retained; definitions, English summaries and qualifications are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
  • S2 Combinatorial Optimization $2012$, Oberwolfach Reports, DOI 10.4171/owr/2011/53, pp. 3003--3076 https://doi.org/10.4171/owr/2011/53.
  • S3 Unique Games research https://arxiv.org/abs/2404.16024.
  • Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.
Preparation and review.
The original source and UnsolvedMath contributors retain attribution for the source extract. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, scope notes and formatting. No new human mathematical authorship or independently verified solution is asserted. Permanent source ID 30001938 and code OWR-11451-013 checked against the complete supplied registry and current repository. Distinct upstream records, including repeated questions and broad or damaged extracts, are retained for complete coverage of the source CS category. A repeated record is not a new independent conjecture. Complete mathematical-equivalence and current-literature review has not been performed. Related canonical identities: 43, 30001374. Preparation and final review follow contribution prompts C and D, with source gaps disclosed. Structural and rendering checks do not establish a new theorem or open status.

Literature and context check

The primary report's Steurer discussion on printed pages 3060--3061 concerns algorithms and SDP hierarchies for Unique Games. The retained record repeats the broader conjecture under separate IDs. This attempt proves a simple exact-consistency algorithm and constructs elementary high- and low-value examples; no approximation-gap hardness reduction or resolution of the Unique Games Conjecture is claimed.

Research attempt: Exact-consistency propagation and the gap to promise hardness

Deciding whether every edge can be satisfied
Let an undirected graph have alphabet $[q]$, with each oriented edge $uv$ carrying a permutation $\pi_{uv}$ and the reverse edge its inverse. Satisfaction means $\ell(v)=\pi_{uv}(\ell(u))$. For each connected component choose a root and a spanning tree. For each of the $q$ possible root labels, propagate labels uniquely along that tree and check every remaining edge. This finds a completely satisfying assignment if one exists: any such assignment has one of the tried root labels and is forced along the tree. Conversely every assignment accepted by the checks satisfies every edge. The work is $O(q(|V|+|E|))$ permutation evaluations and comparisons with explicitly represented permutations. Components are handled independently, so one does not enumerate combinations of their root choices.

Every forest is satisfiable by this construction. A connected graph with $m\geq1$ edges and $n$ vertices has an assignment satisfying at least its $n-1$ tree edges, hence value at least $(n-1)/m$. An isolated vertex is automatically satisfiable and requires no ratio. This is useful near a tree but need not be useful in dense graphs.

Unsatisfiable instances can have value arbitrarily near one
On a cycle of length $m\geq3$ with binary alphabet, put equality constraints on all but one edge and inequality on the last. Full consistency is impossible because traversing the cycle would both preserve and flip the root label. Assigning all vertices the same label violates just the inequality edge, so the optimum value is exactly $(m-1)/m$. Thus the exact-consistency algorithm cannot settle the conjectured promise distinction between near-one and near-zero values: rejecting perfect satisfaction is consistent with values tending to one.
Elementary existence of low-value instances
Fix $0<\beta<1$ and choose $q$ with $\log2<\tfrac12\beta\log q$. On the complete graph on $n$ vertices, choose edge permutations independently and uniformly, using one orientation per edge. For a fixed labeling each edge is satisfied with probability $1/q$, independently. If at least $\beta m$ edges are satisfied, some set of $\lceil\beta m\rceil$ edges are all satisfied. A union bound over edge subsets and all $q^n$ labelings gives \[ \Pr(\exists\text{ labeling of value at least }\beta) \leq q^n2^m q^{-\lceil\beta m\rceil} \leq\exp\left(n\log q+m\log2-\beta m\log q\right). \] For $m=n(n-1)/2>2n/\beta$, this is strictly less than one. Hence there exist instances of value below $\beta$. All permutations can in principle be enumerated to find one, but this argument gives no efficient explicit construction or reduction from an NP-complete problem.

The high-value and low-value families prove that the two promise regimes are mathematically nonempty. Producing both kinds separately does not establish computational difficulty of distinguishing them. A polynomial reduction with both completeness and soundness parameters, for the conjecture's full tolerance quantifiers, remains the missing step.

Verification and adversarial audit

The propagation algorithm tries all root labels and checks non-tree edges, rather than assuming local consistency implies global consistency. The odd parity around a cycle gives exactly one necessary unsatisfied edge. The random low-value proof uses independence across edges for a fixed labeling and a subsequent union bound over labelings; it does not incorrectly assume different labelings' events are independent.
Audit corrections.
Separated perfect-consistency testing from near-perfect promise approximation and distinguished existence of hard-looking instances from a hardness reduction.
External computation.
None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The Unique Games Conjecture and its duplicated source target remain unresolved here. Exact satisfiability, elementary density bounds and existence of separated-value examples are auxiliary results, not promise-gap hardness or a contradiction to the conjecture.
Integration review.
Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

Model and contributor disclosure

The parent Codex GPT-6 model has reviewed the written mathematical arguments at their declared scopes. This is model-assisted review, not independent human verification. OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration and repository-format review; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.

Go to contribution →

Earlier contributions