Proof of Theorem 1, §8 — for a fixed label-set size, the Unique Label Cover → MAX-CUT reduction of §8.1 is polynomial-time computable
OpenOptInapprox.MaxCut.reductionGraph_polyTimeFix natural numbers (the label-set size), , , and . Then the map sending a Unique Label Cover instance with label set to the weighted MAX-CUT instance of the §8.1 reduction (reductionGraph) is computable in polynomial time on encodings: there is a function from strings over the Label Cover alphabet to strings over the MAX-CUT alphabet, computable in polynomial time by a one-tape Turing machine, such that
This is the "the reduction runs in polynomial time" part of the proof of Theorem 1: since the label-set size is a constant, the Long Code tables have constant size , and the instance has vertices and at most edges (with multiplicity), each written with symbols, so the output has polynomial length and is produced by nested loops over , pairs of neighbours of , copies, and the constant-size cube.
Formalization Note. Encodings are the ones of the mission's definitions (encULC: in unary and, for every pair in lexicographic order, a non-edge marker or an edge marker followed by the table of ; encMaxCut: the vertex count and the endpoints of every listed edge in unary). The output depends only on data present in (the permutations are consulted only on edges), so is well defined. Polynomial-time computability is Cook's PolyTimeComputable.
import Mathlib import Definitions.Def_OptInapprox_MaxCut_ReductionGraph
namespace OptInapprox.MaxCut
theorem reductionGraph_polyTime (M₀ R K p q : ℕ) :
∃ g : List ULCSym → List MCSym, CookPvsNP.PolyTimeComputable g ∧
∀ L : ULC, L.M = M₀ → g (encULC L) = encMaxCut (reductionGraph L R K p q) := by
sorry
end OptInapprox.MaxCut