op75_subset_compiler_function_correct
theoremverified
The explicit total compiler preserves language membership.
Statement
theorem op75_subset_compiler_function_correct (w : List Bool) :
w ∈ op75_subset_language ↔ op75_subset_compiler_function w ∈ 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 10
- op75_subset_compiler_functionCompile a canonical subset-sum input to the explicit width-three network encoding; map malformed input to the fixed no-instance.
- op75_subset_compiler_semanticsAny total binary function that maps canonical subset-sum instances to their specified networks and maps malformed inputs outside the zero…
- op75_parse_subset_specThe total decoder returns a weight list and target exactly when their canonical encoding equals its input.
- op75_invalid_input_fallback_nonmemberThe encoding of the empty-weight target-one network is a no-instance of the width-three unit-interval zero language.
- 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_parse_subsetDecode a canonical subset-sum bit string, rejecting malformed or trailing data.
- 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…
- Used by 1
- op75_subset_compiler_machine_sufficesIf the explicit compiler is polynomial-time TM2 computable, the claimed subset-sum to network Karp reduction follows.
Lean source view module on GitHub
theorem op75_subset_compiler_function_correct (w : List Bool) : w ∈ op75_subset_language ↔ op75_subset_compiler_function w ∈ relu_width3_unit_interval_zero_language := by apply op75_subset_compiler_semantics op75_subset_compiler_function · intro as t have hp := (op75_parse_subset_spec (op75_subset_encoding as t) as t).2 rfl simp [op75_subset_compiler_function, hp] · intro w hbad cases hp : op75_parse_subset w with | none => simpa [op75_subset_compiler_function, hp] using op75_invalid_input_fallback_nonmember | some value => rcases value with ⟨as, t⟩ have he := (op75_parse_subset_spec w as t).1 hp exact False.elim (hbad ⟨as,t,he⟩)