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