Encoding arbitrary-alphabet CookPvsNP NP languages into binary CookLevin NP languages
ProvedTetrisHard.Rows.cookPvsNP_np_to_cookLevincomplexity-theory
Let be a finite nonempty alphabet and let be a language in in Cook's one-tape Turing machine model. Then there exist a polynomial-time computable block encoding and a binary language such that
Symbols of and of the certificate alphabet are encoded as fixed-width binary blocks, and the one-tape CookPvsNP verifier is simulated step-by-step on a multi-tape CookLevin verifier.
Preamble
import Definitions.Def_CookPvsNP_defs import Definitions.Def_CookLevin_Complexity
Formal statement
namespace TetrisHard.Rows
theorem cookPvsNP_np_to_cookLevin {Sym : Type} [Fintype Sym] [Nonempty Sym]
{L : CookPvsNP.Lang Sym} (hL : L ∈ CookPvsNP.NP Sym) :
∃ (enc : List Sym → List Bool) (L_bin : CookLevin.Language),
CookPvsNP.PolyTimeComputable enc ∧
CookLevin.InNP L_bin ∧
∀ x, x ∈ L ↔ CookLevin.InLang (enc x) L_bin := by sorry
end TetrisHard.Rows
Source
S. Cook, The Complexity of Theorem-Proving Procedures (1971); Garey and Johnson, Computers and Intractability (1979), Section 2.1 (alphabet encoding invariance of P and NP)