AFTD Auto-Formalizing Theoretical Domains

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))
See it in the graphDiscuss this resultChallenge it