AFTD Auto-Formalizing Theoretical Domains

op75_subset_language

def

The language of canonical binary words encoding a finite list of nonnegative integer weights and a target that is a subset sum of the list.

Statement

def op75_subset_language : Language 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 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…
  • 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.
Used by 5

Lean source view module on GitHub

def op75_subset_language : Language Bool := {w | ∃ as : List ℕ, ∃ t : ℕ, op75_subset_encoding as t = w ∧ op75_subset (as.map fun a => (a : ℝ)) (t : ℝ)}
See it in the graphDiscuss this resultChallenge it