op75_subset_encoding
def
The source word encodes each nonnegative integer weight as a true marker followed by its self-delimiting natural encoding, then a false marker and the target natural encoding.
Statement
def op75_subset_encoding (as : List ℕ) (t : ℕ) : List Bool- Source
- OP-75 one-pass subset-sum construction, arXiv:2610.06092; binary source encoding for a machine-level reduction.
- Verified
- 15 Nov 2026
- Axioms
- none listed
- Built on 1
- 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 10
- op75_parse_subset_specThe total decoder returns a weight list and target exactly when their canonical encoding equals its input.
- op75_subset_encoding_length_lowerThe number of weights is at most the bit length of the encoded instance.
- op75_subset_encoding_consEncoding a nonempty weight list emits its marker, the head natural, then the remaining instance.
- op75_subset_encoding_injectiveThe binary source encoding uniquely determines the finite list of weights and the target.
- 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_semanticsAny total binary function that maps canonical subset-sum instances to their specified networks and maps malformed inputs outside the zero…
- op75_subset_compiler_function_correctThe explicit total compiler preserves language membership.
- op75_parse_subset_aux_soundEvery successful fuel-bounded parse reconstructs exactly the original canonical subset-sum word.
- op75_parse_subset_aux_completeSufficient fuel makes the parser accept every canonical instance and return its weights and target.
- 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.
Lean source view module on GitHub
def op75_subset_encoding (as : List ℕ) (t : ℕ) : List Bool := (as.flatMap fun a => true :: relu_encode_nat a) ++ [false] ++ relu_encode_nat t