Verified polynomial-time reductions in Lean 4: formalizing the complexity of decision-relevant information

We present a Lean 4 framework for polynomial-time reductions and complexity-theory proofs, and use it to formalize the complexity of identifying decision-relevant information. Problem: given a decision problem, which coordinates suffice to compute an optimal action? (SUFFICIENCY-CHECK; explicit encodings). Verified complexity results (Lean): coNP-complete; $(1-\varepsilon)\ln n$ inapproximable (from SET-COVER); $2^{Ω(n)}$ lower bounds under ETH for succinct encodings; W[2]-hard for a natural parameterization; and a dichotomy between explicit and succinct models. Formalization contributions: bundled Karp reductions with polynomial-time witnesses; composition lemmas/tactics; and templates for NP/coNP and $Σ_2^P$ membership and hardness. Scale: about 5,600 lines of Lean across 36 files, with 230+ theorems and explicit polynomial bounds.

arxiv.org · arXiv.org