op75_subset_compiler_semantics
theoremverified
Any total binary function that maps canonical subset-sum instances to their specified networks and maps malformed inputs outside the zero language preserves membership in both directions. The result does not assume encoding injectivity or polynomial-time computability.
Statement
theorem op75_subset_compiler_semantics (f : List Bool → List Bool)
(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) :
∀ w, w ∈ op75_subset_language ↔ f w ∈ relu_width3_unit_interval_zero_language- Source
- OP-75: semantic correctness for the subset-sum to width-three ReLU network reduction.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- 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_network_subset_sumFor any finite list of nonnegative integer weights and nonnegative integer target, the explicitly constructed width-three ReLU network has…
- relu_width3_language_mem_iffSanity check of the language: the encoding of a width-3 ReLU network lies in the verification language exactly when the network has a zero…
- 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_subsetA real target belongs to the subset sums of a list when it can be obtained recursively by either omitting or including the first weight.
- 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_encodingThe source word encodes each nonnegative integer weight as a true marker followed by its self-delimiting natural encoding, then a false…
- 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_network_has_unit_interval_zeroA feedforward ReLU neural network
netof width $k$ has a zero in the unit interval $[0, 1]$ if there exists some real number…
- Used by 2
- op75_subset_compiler_correct_reductionA total polynomial-time Boolean compiler with the specified canonical output and a no-instance output on malformed words gives the desired…
- op75_subset_compiler_function_correctThe explicit total compiler preserves language membership.
Lean source view module on GitHub
theorem op75_subset_compiler_semantics (f : List Bool → List Bool) (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) : ∀ w, w ∈ op75_subset_language ↔ f w ∈ relu_width3_unit_interval_zero_language := by intro w constructor · rintro ⟨as, t, rfl, hs⟩ rw [hgood, relu_width3_language_mem_iff, op75_compact_network_subset_sum] exact hs · intro hw by_cases hc : ∃ as : List ℕ, ∃ t : ℕ, op75_subset_encoding as t = w · obtain ⟨as, t, he⟩ := hc refine ⟨as, t, he, ?_⟩ rw [← he, hgood, relu_width3_language_mem_iff, op75_compact_network_subset_sum] at hw exact hw · exact False.elim (hbad w hc hw)