Perfect completeness for 2-to-1 games

What OpenAI claims

Proves Khot's 2-to-1 Games Conjecture with perfect completeness: for every fixed rational δ ∈ (0,1), it is NP-hard to distinguish satisfiable games from games whose optimum is at most δ, on explicit unweighted instances. The alphabet depends only on δ, and every right-hand label has exactly two preimages under each constraint map. (Lean)

Paper

1. Perfect completeness for 2-to-1 games

   23 September 2026 · Preprint, not peer reviewed · PDF

   OpenAI's abstract We prove the 2-to-1 Games Conjecture with perfect completeness. For every fixed rational δ ∈ (0,1), it is NP-hard to distinguish satisfiable 2-to-1 games from games of value at most δ, with a fixed alphabet and an explicitly listed unweighted multiset of constraints.

Status

Preprint. The paper has not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.