AFTD Auto-Formalizing Theoretical Domains

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⟩
See it in the graphDiscuss this resultChallenge it