AFTD Auto-Formalizing Theoretical Domains

op75_subset_reduction_hard

theoremverified

If the canonical subset-sum source language is NP-hard and reduces in polynomial time to the width-three zero language, then the width-three zero language is NP-hard.

Statement

theorem op75_subset_reduction_hard (hsource : NPHard op75_subset_language) (hred : KarpReducible Bool Bool op75_subset_language relu_width3_unit_interval_zero_language) : NPHard relu_width3_unit_interval_zero_language
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 7
  • NPHardA language L over an alphabet Γ is NP-hard if every language L' that is in NP Karp-reduces to L, the languages L' ranging over all…
  • 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_subset_languageThe language of canonical binary words encoding a finite list of nonnegative integer weights and a target that is a subset sum of the list.
  • relu_width3_unit_interval_zero_languageThe verification language at width 3 on the unit interval, for the fixed encoding relu_network3_encode: the set of Bool words w such that…
  • op75_karp_reducible_transPolynomial-time many-one reducibility is transitive for languages over arbitrary alphabets under the repository TM2 definition.
  • op75_karp_bool_transPolynomial-time many-one reductions compose when their intermediate language uses the Boolean alphabet, even if the source and target…
  • NondeterministicPolyTimeBoundedA language L over Γ is in NP in verifier form if there are a polynomial p and a language V of words over Γ ⊕ Unit such that V is decidable…

Lean source view module on GitHub

theorem op75_subset_reduction_hard (hsource : NPHard op75_subset_language) (hred : KarpReducible Bool Bool op75_subset_language relu_width3_unit_interval_zero_language) : NPHard relu_width3_unit_interval_zero_language := by
  intro Γ L hL
  exact op75_karp_bool_trans Γ Bool L op75_subset_language relu_width3_unit_interval_zero_language
    (hsource Γ L hL) hred
See it in the graphDiscuss this resultChallenge it