Many approximation problems resist the standard PCP toolkit: the best known NP-hardness factors for Max-Cut, Vertex-Cover and approximate graph colouring are far from the best known polynomial-time algorithms. To explain this gap, Khot (CCC 2002) proposed the Unique-Games Conjecture and the family of -to-1 Games Conjectures. The -to-1 conjectures assert perfect completeness: the hard instances are either fully satisfiable, or satisfiable only to a vanishing extent. Perfect completeness is what makes these conjectures usable for colouring problems, where a "yes" instance must be genuinely -colourable rather than almost so.
A line of work culminating in Khot–Minzer–Safra and Dinur–Khot–Kindler–Minzer–Safra established the almost-perfect completeness version for -to-1 games: for every there is an alphabet bound such that distinguishing value from value is NP-hard. Their route goes through Håstad's hardness for linear equations, which cannot have perfect completeness, so the loss is intrinsic to the technique. The source paper of this mission removes that loss for .
A label-cover instance (Definition 1.1 of the source) consists of a bipartite graph , two finite alphabets , and for each edge a constraint . The constraint is a projection constraint if there is with , and a -to-1 constraint if in addition for every . Given assignments and , the fraction of satisfied edges is , and
An instance all of whose constraints are -to-1 is a -to-1 game.
For , is the promise problem: given a -to-1 game with both alphabets of size at most , distinguish from . Writing for the same promise problem over all projection instances, the PCP theorem together with the parallel repetition theorem gives that is NP-hard for a suitable (Theorem 1.2 of the source); this mission takes that statement as an external input.
In Lean this is stated as a polynomial-time gap-preserving reduction: for every there is a soundness threshold such that for every source alphabet bound there is a target alphabet bound and a polynomial-time computable map sending projection label-cover instances with alphabets of size at most and value to -to-1 games with alphabets of size at most and value , and instances of value at most to -to-1 games of value at most . Combined with the NP-hardness of , this is exactly Theorem 1.6.
The milestone list follows the source's own numbering: the hardness of approximate colouring of -uniform hypergraphs that starts the construction (Theorem 3.1), the two Grassmann decoding theorems the inner PCP rests on (Theorems 3.2 and 3.3), the sunflower bound on zoom-outs (Lemma 3.8), and the linear-algebraic layer connecting NAE-satisfying bilinear forms with their tensor decompositions (Propositions 4.13, 4.14 and Corollary 4.15).
Theorem 1.6 confirms the -to-1 Games Conjecture, the first of Khot's -to-1 conjectures to be settled with perfect completeness. Via known reductions it yields: for every , it is NP-hard to -colour a -colourable graph (previously known for ); for every , it is NP-hard to find an independent set of relative size in a -colourable -uniform hypergraph; and hardness results for low-rank matrix completion.
None of this material is formalized today. Mathlib has no label cover, no PCP machinery, no Grassmann graph and no complexity classes beyond the computability layer. A complete development therefore contributes reusable infrastructure — finite two-prover games and their value, gap-preserving reductions, the Grassmann graph over and its agreement tests — well beyond this single theorem.
The obvious attempt is to redo the -to-1 construction with a perfectly complete outer PCP, namely hardness of systems of quadratic equations over in place of linear ones. This fails at composition: the Grassmann agreement test, the only known device that produces -to-1 constraints, is a test for linear functions and cannot certify quadratic constraints. Linearizing the quadratic equations by a low-rank test destroys the covering property of the outer PCP, which is what makes the composed soundness analysis work. The source paper's answer is a three-layer construction (outer, middle and inner PCP) with a lazy parallel repetition in the middle layer and an inner PCP based on a tensor of the standard Grassmann encoding with Golowich's low-rank variant.
All objects are finite and explicit. A label-cover instance carries left vertices , right vertices , alphabets and , a finite edge set, and a projection map for every pair of vertices; only projection instances are representable, as in Definition 1.1. The value is the supremum over all pairs of assignments of the fraction of satisfied edges, taken in ; when there are no edges, or no assignments at all, the convention gives value . A tripled set (Definition 4.1) is modelled as , with the triple indexed by being . The Grassmann objects live in modelled as , and all probabilities are ratios of cardinalities of finite sets of subspaces, with the convention that an empty denominator gives .
Hardness is not stated as "NP-hard" — no notion of NP is available — but as the existence
of a reduction. This matters: a reduction required only to preserve the gap, with no
computability condition, would be trivially satisfiable by a map that inspects the value of
its input and returns one of two fixed instances. The formalization therefore requires the
reduction map to be computed by a Turing machine within a polynomial time bound, using
Mathlib's Turing.TM2ComputableInPolyTime together with an explicit binary encoding of
instances. The NP-hardness of the source problem (Theorem 1.2,
i.e. the PCP theorem plus parallel repetition) is an external input and is not part of this
mission.
Contributions of intermediate infrastructure are welcome: the games of Sections 4–6 (Game1a, Game1b, Game2a, Game2b, Game2c, Game3) and their completeness and soundness lemmas are the natural next layer of milestones, as are the covering properties of Appendix C and the list-decoding bounds of Appendix E.
namespace FourToOneGames
theorem four_to_one_perfect_completeness :
∀ ε : ℝ, 0 < ε → ∃ s : ℝ, 0 < s ∧ s < 1 ∧ ∀ r₀ : ℕ, ∃ r : ℕ,
Nonempty (GapReduction encodeLabelCover encodeLabelCover
(fun P : LabelCover => LabelCover.AlphabetBound r₀ P ∧ P.val = 1)
(fun P : LabelCover => LabelCover.AlphabetBound r₀ P ∧ P.val ≤ s)
(fun Q : LabelCover =>
LabelCover.AlphabetBound r Q ∧ LabelCover.IsDToOne 4 Q ∧ Q.val = 1)
(fun Q : LabelCover =>
LabelCover.AlphabetBound r Q ∧ LabelCover.IsDToOne 4 Q ∧ Q.val ≤ ε)) := by
sorry
end FourToOneGamesThe 4-to-1 Games Conjecture for (Khot, CCC 2002), with perfect completeness. For all there exists such that is NP-hard: given a -to-1 game with alphabets of size at most , it is NP-hard to distinguish from .
Hardness is formalized as a polynomial-time gap-preserving reduction from label cover with projection constraints: for every there is a soundness threshold such that for every source alphabet bound there are a target alphabet bound and a polynomial-time computable map with always a -to-1 game over alphabets of size at most , such that implies (perfect completeness) and implies . Composed with the NP-hardness of — the PCP theorem plus the parallel repetition theorem, Theorem 1.2 of the source, which this mission takes as an external input — this is exactly Theorem 1.6.
The polynomial-time computability requirement is essential: without it the statement would be satisfied by a map that inspects the value of its input and returns one of two fixed instances.
No open leaves. Every sub-goal is proved or awaiting decomposition.