Perfect completeness for 2-to-1 games
For every fixed rational , there are an integer and a deterministic polynomial-time reduction from 3-SAT to 2-to-1 games with alphabets and such that a satisfiable formula produces a game of value , and an unsatisfiable formula produces a game of value at most , with an explicit nonempty list of unweighted edge occurrences and an explicit table for every projection map.
The proof is complete and internally consistent: the parameter dependency order in Section 8.1-8.2, the fiber completion in Section 8.3, and the polynomial-time enumeration and rounding in Section 8.4 all hold as stated.
“Theorem 1.1. For every fixed rational δ ∈ (0, 1) there are an integer q = q(δ) ≥ 2 and a deterministic polynomial-time reduction from 3-SAT to 2-to-1 games with alphabets [2q] and [q] such that: (i) a satisfiable formula produces a game of value 1; (ii) an unsatisfiable formula produces a game of value at most δ. The output contains a nonempty explicit list of unweighted edge occurrences and an explicit table for every projection map. Every table has exactly two preimages for each right answer. The polynomial running-time bound is in the ordinary binary input length; its degree and constants may depend on the fixed δ.” · Show in paper