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
- op75_subset_reduction_hardIf the canonical subset-sum source language is NP-hard and reduces in polynomial time to the width-three zero language, then the…
- 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_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
def op75_subset_language : Language Bool := {w | ∃ as : List ℕ, ∃ t : ℕ, op75_subset_encoding as t = w ∧ op75_subset (as.map fun a => (a : ℝ)) (t : ℝ)}