AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it