AFTD Auto-Formalizing Theoretical Domains

op75_subset_compiler_correct_reduction

theoremverified

A total polynomial-time Boolean compiler with the specified canonical output and a no-instance output on malformed words gives the desired Karp reduction.

Statement

theorem op75_subset_compiler_correct_reduction (f : List Bool → List Bool)
    (hf : Nonempty (Turing.TM2ComputableInPolyTime (id : List Bool → List Bool) (id : List Bool → List Bool) f))
    (hgood : ∀ (as : List ℕ) (t : ℕ),
      f (op75_subset_encoding as t) = relu_network3_encode (op75_compact_network as t))
    (hbad : ∀ w, (¬ ∃ as : List ℕ, ∃ t : ℕ, op75_subset_encoding as t = w) →
      f w ∉ relu_width3_unit_interval_zero_language) :
    KarpReducible Bool Bool op75_subset_language relu_width3_unit_interval_zero_language
Source
OP-75: separate the finite-machine compiler obligation from semantic correctness of the reduction.
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • op75_subset_compiler_semanticsAny total binary function that maps canonical subset-sum instances to their specified networks and maps malformed inputs outside the zero…
  • 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_encodingThe source word encodes each nonnegative integer weight as a true marker followed by its self-delimiting natural encoding, then a false…
  • relu_network3_encodeEncoding of a width-3 ReLU network as a Bool word, of length linear in the total bit length of its rational entries: input weights, input…
  • 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_compact_networkThe width-three network obtained by concatenating a seven-layer block for each integer weight, followed by the final target-checking layer…
  • 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…

Lean source view module on GitHub

theorem op75_subset_compiler_correct_reduction (f : List Bool → List Bool)
    (hf : Nonempty (Turing.TM2ComputableInPolyTime (id : List Bool → List Bool) (id : List Bool → List Bool) f))
    (hgood : ∀ (as : List ℕ) (t : ℕ),
      f (op75_subset_encoding as t) = relu_network3_encode (op75_compact_network as t))
    (hbad : ∀ w, (¬ ∃ as : List ℕ, ∃ t : ℕ, op75_subset_encoding as t = w) →
      f w ∉ relu_width3_unit_interval_zero_language) :
    KarpReducible Bool Bool op75_subset_language relu_width3_unit_interval_zero_language := by
  exact ⟨f, hf, op75_subset_compiler_semantics f hgood hbad⟩
See it in the graphDiscuss this resultChallenge it