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