Skip to content

Documentary state: DRAFT_UNACCEPTED. This draft has NOT been editorially admitted. Mathematical claims require independent checking.

OAI-26 family 102: Unique Games and sharp approximation-hardness claims

Editorial status: DRAFT_UNACCEPTED. NO_CERTIFICATION. This account reports source-pinned publisher claims; it does not independently validate any complexity-theoretic proof.

The question in plain language

Some optimization problems are easy to state but hard to solve exactly. Approximation algorithms instead seek solutions close to the best possible value. A hardness threshold identifies how close an efficient algorithm could get before a standard complexity assumption would imply that no such algorithm exists.

The Unique Games Conjecture (UGC) concerns a special family of constraint-satisfaction problems in which each edge constraint specifies a permutation of possible labels. It has long served as a conditional foundation for many proposed sharp approximation thresholds. Family 102 claims a resolution of the conjecture and separately claims direct NP-hardness results for four graph problems.

A small example

In Max-Cut, divide a graph's vertices into two groups to maximize the number of edges crossing between them. A random partition cuts about half the edges on average; sophisticated algorithms achieve a stronger guaranteed ratio. The Goemans–Williamson semidefinite-programming algorithm has an approximation factor approximately \(0.87856\).

To say this ratio is optimal under NP-hardness assumptions is different from exhibiting the approximation algorithm. It requires an appropriate reduction proving that any polynomial-time algorithm achieving a better guaranteed factor would also solve NP-hard instances beyond the allowed gap. The distinction matters further because a conditional UGC implication and an independent direct reduction are different mathematical statements.

What is known

The protected Family 102 catalogue identifies five manuscripts: a Unique Games theorem and direct hardness constructions for Max-Cut, Vertex Cover, Min-UnCut, and directed feedback vertex set.

The pinned publisher overview claims a proof of Khot's Unique Games Conjecture. It separately says that direct reductions, based on established PCP and Label Cover hardness, establish these NP-hardness boundaries on unweighted graphs:

  • Max-Cut: approximation better than the Goemans–Williamson ratio.
  • Vertex Cover: approximation better than factor two.
  • Min-UnCut: approximation within any fixed constant factor.
  • Directed feedback vertex set: approximation within any fixed constant factor.

The direction of a ratio depends on whether a problem is being maximized or minimized. Max-Cut seeks a larger objective; the other three seek smaller objectives, so the threshold descriptions must not be interchanged. The overview distinguishes the direct reductions from any dependence on the claimed UGC theorem; it does not establish here that every consequence often associated with UGC follows from the five manuscripts.

GCL verification state

The five manuscripts are source-locked to openai/math@1581d4cbdd69a0faf34b2089614fe2a814316a6a in the protected GCL catalogue. The overview provides the above result claims but not, by itself, a verified theorem-by-theorem derivation.

This documentary pass has not independently inspected all proof steps, PCP or Label Cover prerequisites, the exact UGC promise gap and alphabet quantifiers, reduction completeness and soundness, randomization or encoding assumptions, or whether the NP-hardness conclusions use deterministic many-one reductions. No Family 102-specific GCL Comparator result, trusted formal proof, critical proof audit, or MATHCERT certificate is asserted.

What remains

Audit the Unique Games manuscript from its exact theorem statement through the proof and source dependencies; distinguish a full resolution from a restricted-parameter result. For each direct reduction, extract the domain of instances, the promise gap, the objective normalization and its inequality direction, and the complexity assumption. Verify unweighted graph restrictions and any use of multigraphs, loops, gadget weights, parallel edges or directedness.

For Max-Cut, compare the exact claimed hardness factor with the mathematical Goemans–Williamson constant and its strict inequality. For Vertex Cover, verify the interpretation of the factor-two limit. For Min-UnCut and directed feedback vertex set, check the quantifiers behind “any fixed constant factor” and the treatment of zero optima.

Complete mathematical Markdown and HTML regression tests, source-critical editorial review, and protected merge/readback. Documentary admission is not a mathematical or complexity-theoretic certification.

Sources and claim boundaries

Boundary: NO_CERTIFICATION. Claimed resolutions and NP-hardness theorems remain attributed to the publisher pending independent proof verification.


Indexed primary manuscript paths: