op75_karp_bool_trans
theoremverified
Polynomial-time many-one reductions compose when their intermediate language uses the Boolean alphabet, even if the source and target alphabets are arbitrary.
Statement
theorem op75_karp_bool_trans (Γ₀ Γ₂ : Type) (L₀ : Language Γ₀) (L₁ : Language Bool) (L₂ : Language Γ₂) : KarpReducible Γ₀ Bool L₀ L₁ → KarpReducible Bool Γ₂ L₁ L₂ → KarpReducible Γ₀ Γ₂ L₀ L₂
- Source
- OP-75 reduction composition with the canonical Boolean subset-sum source language.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- KarpReducibleA language L over an alphabet Γ Karp-reduces (polynomial-time many-one reduces) to a language L' over an alphabet Γ' if there is a…
- op75_tm2_output_linear_boundFor any finite TM2, there is a constant C such that for every input and output, a halting run of at most n steps has output length at most…
- op75_tm2_bool_compPolynomial-time finite stack machines compose when their intermediate alphabet is Boolean, for arbitrary input and output alphabets.
- Used by 1
- op75_subset_reduction_hardIf the canonical subset-sum source language is NP-hard and reduces in polynomial time to the width-three zero language, then the…
Lean source view module on GitHub
theorem op75_karp_bool_trans (Γ₀ Γ₂ : Type) (L₀ : Language Γ₀) (L₁ : Language Bool) (L₂ : Language Γ₂) : KarpReducible Γ₀ Bool L₀ L₁ → KarpReducible Bool Γ₂ L₁ L₂ → KarpReducible Γ₀ Γ₂ L₀ L₂ := by rintro ⟨f, hf, hL⟩ ⟨g, hg, hM⟩ refine ⟨g ∘ f, op75_tm2_bool_comp hf hg, ?_⟩ intro w exact (hL w).trans (hM (f w))