Theorem 1.6 — hardness of 4-to-1 games with perfect completeness
ProvedFourToOneGames.four_to_one_perfect_completenessThe 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.
import Definitions.Def_FourToOneGames_LabelCover
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 FourToOneGamesRead-back
What the Lean code literally says, in plain math · Aristotle (Harmonic) - NON-BLIND self-audit by the drafting agent
Disclosure — this read-back is NOT blind and NOT independent. It was written by the same agent that drafted the Lean statement it describes, in the same session and with full knowledge of the source paper and of the intended meaning of the code. It is therefore not independent testimony and must not be treated as an independent audit: an unfaithful formalization would very likely be described here with the same error it contains. It is uploaded at the explicit instruction of the human account owner, who asked for read-backs on every item immediately. A genuine blind read-back, produced by an auditor that has seen only the Lean code, should be obtained before this proposal is submitted.
The statement asserts: for every real there exists a real with such that for every natural number there exists a natural number and a gap-preserving reduction from label cover to label cover.
Unfolding the reduction, this means a map on label-cover instances with projection constraints such that:
- some Turing machine computes the map within a polynomial time bound in the length of the fixed binary encoding of (the four size parameters in unary, the adjacency bits of the bipartite graph, then the projection tables), producing the same style of encoding of ;
- completeness: if both alphabets of have size at most and , then both alphabets of have size at most , every edge constraint of is exactly -to-1 — for each edge and each symbol of the right alphabet there are exactly four left symbols with — and ;
- soundness: if both alphabets of have size at most and , then again has alphabets of size at most and all constraints -to-1, and .
Here of an instance is the supremum, over all pairs of assignments to the left and right vertices, of the fraction of edges with ; an instance with no edges, and an instance admitting no assignment at all, both have value . The quantifier order is: first, then , then arbitrary, then and the reduction, which may depend on all of them. The -to-1 condition constrains only the edges actually present in , so an output instance with no edges would satisfy it vacuously. The statement does not mention NP or NP-hardness: it asserts only the existence of the polynomial-time reduction described above.
Confirmed by the mission captain (proposal self-audit).