3-SAT is NP-hard under CookPvsNP many-one reductions
ProvedTetrisHard.Rows.ksat3_cookPvsNP_npHardcomplexity-theory
For every finite nonempty alphabet and every language in (in Cook's one-tape Turing machine model), is polynomial-time many-one reducible to binary-encoded 3-SAT:
This bridges the Cook–Levin 3-SAT NP-completeness theorem (KSat.ksat_npComplete 3) into the CookPvsNP complexity framework by encoding arbitrary finite alphabets into fixed-width binary blocks, simulating Cook's one-tape verifier in the CookLevin model, and compiling the resulting polynomial-time CookLevin reduction machine into a CookPvsNP Turing machine via stack programs.
Preamble
import Definitions.Def_CookPvsNP_defs import Definitions.Def_KSat_Languages
Formal statement
namespace TetrisHard.Rows
theorem ksat3_cookPvsNP_npHard :
∀ (Sym : Type) [Fintype Sym] [Nonempty Sym] (L : CookPvsNP.Lang Sym),
L ∈ CookPvsNP.NP Sym →
CookPvsNP.PolyReducible L {w : List Bool | KSat.KSAT 3 w} := by sorry
end TetrisHard.Rows
Source
S. Cook, The Complexity of Theorem-Proving Procedures (1971); Garey and Johnson, Computers and Intractability (1979), Section 2.6 and Theorem 3.1