AFTD Auto-Formalizing Theoretical Domains

op75_karp_reducible_trans

theoremverified

Polynomial-time many-one reducibility is transitive for languages over arbitrary alphabets under the repository TM2 definition.

Statement

theorem op75_karp_reducible_trans (Γ₀ Γ₁ Γ₂ : Type) (L₀ : Language Γ₀) (L₁ : Language Γ₁) (L₂ : Language Γ₂) : KarpReducible Γ₀ Γ₁ L₀ L₁ → KarpReducible Γ₁ Γ₂ L₁ L₂ → KarpReducible Γ₀ Γ₂ L₀ L₂
Source
OP-75 complexity reduction; transitivity of polynomial-time many-one reductions for the repository TM2 model.
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_inhabited_compPolynomial-time finite stack machines compose whenever their intermediate alphabet is inhabited; the input and output alphabets are…
  • op75_tm2_empty_compPolynomial-time finite stack machines compose when their intermediate alphabet is empty, 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_reducible_trans (Γ₀ Γ₁ Γ₂ : Type) (L₀ : Language Γ₀) (L₁ : Language Γ₁) (L₂ : Language Γ₂) : KarpReducible Γ₀ Γ₁ L₀ L₁ → KarpReducible Γ₁ Γ₂ L₁ L₂ → KarpReducible Γ₀ Γ₂ L₀ L₂ := by
  classical
  rintro ⟨f, hf, h₁⟩ ⟨g, hg, h₂⟩
  refine ⟨g ∘ f, ?_, fun w => (h₁ w).trans (h₂ (f w))⟩
  by_cases h : Nonempty Γ₁
  · letI : Inhabited Γ₁ := ⟨Classical.choice h⟩
    exact op75_tm2_inhabited_comp hf hg
  · letI : IsEmpty Γ₁ := ⟨fun x => h ⟨x⟩⟩
    exact op75_tm2_empty_comp hf hg
See it in the graphDiscuss this resultChallenge it