1 · The essentials
The result concerns puzzles in which labels must be chosen to satisfy a list of rules. Each rule maps labels on one side to labels on the other, with exactly two labels mapping to each possible label on the receiving side. The task is to tell apart puzzles where every rule can be satisfied from puzzles where even the best choices satisfy only a small fraction. The manuscript establishes a formal computational hardness result for this distinction. That result holds for every fixed rational threshold strictly between zero and one, with the available labels depending only on that threshold. The rules are listed explicitly and counted equally, though repetitions are allowed. The main result has a Lean formalization.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine assigning badges to people on two sides of a room, with a checklist specifying which badge pairings are acceptable. Each badge on the receiving side accepts exactly two badges from the other side, and the challenge is to distinguish a checklist that can be met completely from one where only a small fraction can be met.
Why it matters
The manuscript addresses Khot’s 2-to-1 Games Conjecture with perfect completeness: the fully satisfiable case remains difficult to distinguish from a case with a low achievable score. The statement includes explicit, equally weighted constraint lists and an alphabet whose size depends only on the chosen threshold. These conditions specify the form of the instances covered by the hardness result.
2 · Going further
A 2-to-1 game asks for label choices satisfying constraints between a left side and a right side. Each constraint map has exactly two preimages for every right-hand label. The value, or optimum, is the largest fraction of constraints that can be satisfied simultaneously. The precise statement is that, for every fixed rational , it is NP-hard to distinguish games of value from games of value at most .
The source identifies this as the 2-to-1 Games Conjecture, attributed to Khot, with perfect completeness. Here perfect completeness refers to the value- side of the distinction: those instances are fully satisfiable, rather than merely close to satisfiable. For each fixed threshold, the alphabet is fixed and depends only on . Constraints form an explicitly listed, unweighted multiset, so repeated occurrences are permitted and are counted equally.
The supplied abstract states the result but does not describe the construction or the main steps of the argument, so no proof strategy can be extracted from it. The main manuscript is marked as Lean-formalized, and the main result has a Lean formalization. No companion manuscripts or relationships to companion results are supplied.
Useful notions
- Label assignments and constraint satisfaction
- Functions and preimages
- Fractions of satisfied constraints
- NP-hardness
- Formal verification in Lean
What was known before / what is new
Before
The source identifies the target statement as Khot’s 2-to-1 Games Conjecture. It gives no account of earlier partial results or of which versions were previously available.
New
The main manuscript establishes the conjecture with perfect completeness for every fixed rational . Its statement uses a fixed alphabet depending only on and an explicitly listed unweighted multiset of constraints. The main result has a Lean formalization.
Limits and assumptions
The stated threshold must be fixed, rational, and strictly between zero and one; the alphabet may depend on that threshold. Every constraint map must have exactly two preimages for each right-hand label. The hardness distinction concerns fully satisfiable instances versus instances of optimum at most ; no classification is specified for intermediate values. The main result is Lean-formalized, but the supplied material does not describe the formalization’s internal scope or the argument’s details. It lists no remaining open questions.
Mini glossary
- Alphabet —
- The set of labels available for assignments in a game.
- Preimage —
- A label that a constraint map sends to a specified label on the receiving side.
- Game value —
- The largest fraction of constraints that any label assignment can satisfy.
- Perfect completeness —
- The requirement that instances on the satisfiable side of the hardness distinction allow every constraint to be satisfied.
- Unweighted multiset of constraints —
- A collection of constraints in which repetitions are allowed and every occurrence is counted equally.
- Lean formalization —
- An encoding of a mathematical result and its proof for verification in Lean.
Keywords : 2-to-1 games · Perfect completeness · NP-hardness
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Proves Khot's 2-to-1 Games Conjecture with perfect completeness: for every fixed rational , 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.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Perfect completeness for 2-to-1 games
23/09/2026We prove the 2-to-1 Games Conjecture with perfect completeness. For every fixed rational , 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.