op75_subset_encoding_length_lower
theoremverified
The number of weights is at most the bit length of the encoded instance.
Statement
lemma op75_subset_encoding_length_lower (as : List ℕ) (t : ℕ) :
as.length ≤ (op75_subset_encoding as t).length- Source
- OP-75: canonical subset-sum input decoder for the width-three ReLU compiler.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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_encode_natBinary encoding of a natural number as a self-delimiting Bool word: each base-2 digit, least significant first, is preceded by a true…
- Used by 1
- op75_parse_subset_specThe total decoder returns a weight list and target exactly when their canonical encoding equals its input.
Lean source view module on GitHub
lemma op75_subset_encoding_length_lower (as : List ℕ) (t : ℕ) : as.length ≤ (op75_subset_encoding as t).length := by have h : as.length ≤ (as.flatMap (fun a => true :: relu_encode_nat a)).length := by induction as with | nil => simp | cons a as ih => simp only [List.length_cons, List.flatMap_cons, List.length_append] at * omega simp only [op75_subset_encoding, List.length_append, List.length_cons, List.length_nil] omega