Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Encoding arbitrary-alphabet CookPvsNP NP languages into binary CookLevin NP languages

Proved
TetrisHard.Rows.cookPvsNP_np_to_cookLevin

by kmehltretter82 · Nov 19, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theory

Let Σ\SigmaΣ be a finite nonempty alphabet and let L⊆Σ∗L \subseteq \Sigma^*L⊆Σ∗ be a language in NP(Σ)\mathrm{NP}(\Sigma)NP(Σ) in Cook's one-tape Turing machine model. Then there exist a polynomial-time computable block encoding enc:Σ∗→{0,1}∗\mathrm{enc} : \Sigma^* \to \{0,1\}^*enc:Σ∗→{0,1}∗ and a binary language Lbin∈NPCLL_{\mathrm{bin}} \in \mathrm{NP}_{\mathrm{CL}}Lbin​∈NPCL​ such that

∀ x∈Σ∗,x∈L  ⟺  enc(x)∈Lbin.\forall\, x \in \Sigma^*,\qquad x \in L \iff \mathrm{enc}(x) \in L_{\mathrm{bin}}.∀x∈Σ∗,x∈L⟺enc(x)∈Lbin​.

Symbols of Σ\SigmaΣ 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)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me