op75_subset_compiler_machine_suffices
theoremverified
If the explicit compiler is polynomial-time TM2 computable, the claimed subset-sum to network Karp reduction follows.
Statement
theorem op75_subset_compiler_machine_suffices
(h : Nonempty (Turing.TM2ComputableInPolyTime (id : List Bool → List Bool)
(id : List Bool → List Bool) op75_subset_compiler_function)) :
KarpReducible Bool Bool op75_subset_language relu_width3_unit_interval_zero_language- Source
- OP-75: explicit total subset-sum to width-three network compiler.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- op75_subset_compiler_function_correctThe explicit total compiler preserves language membership.
- KarpReducibleA language L over an alphabet Γ Karp-reduces (polynomial-time many-one reduces) to a language L' over an alphabet Γ' if there is a…
- 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_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.
- op75_subset_compiler_functionCompile a canonical subset-sum input to the explicit width-three network encoding; map malformed input to the fixed no-instance.
Lean source view module on GitHub
theorem op75_subset_compiler_machine_suffices (h : Nonempty (Turing.TM2ComputableInPolyTime (id : List Bool → List Bool) (id : List Bool → List Bool) op75_subset_compiler_function)) : KarpReducible Bool Bool op75_subset_language relu_width3_unit_interval_zero_language := by exact ⟨op75_subset_compiler_function, h, op75_subset_compiler_function_correct⟩