AFTD Auto-Formalizing Theoretical Domains

SubsetSumToPartition.partitionWeight

defimported Lean

The weight function on the augmented universe $U \oplus \mathrm{Bool}$ built from a Subset Sum instance $(w, T)$. Writing $W = \sum_{a} w(a)$, it sends the original item $\mathrm{inl}\,a$ to $w(a)$, the first dummy item $\mathrm{inr}\,\mathsf{true}$ to $2W - T$, and the second dummy item $\mathrm{inr}\,\mathsf{false}$ to $W + T$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {U : Type*} [Fintype U] [DecidableEq U] in
def SubsetSumToPartition.partitionWeight (w : U → ℕ) (T : ℕ) : U ⊕ Bool → ℕ
Defined in
TCSlib, `SubsetSumToPartition.partitionWeight`
Lean proof
By Hydroxyi (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
none listed
Used by 3

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {U : Type*} [Fintype U] [DecidableEq U] in
/-- Reduction from Subset Sum to Partition. We create a new type `B` by taking the disjoint union of `U` and `Bool`. `U ⊕ Bool` acts as our new set, adding exactly two new "dummy" items: - `Sum.inl a` represents the original elements from `A`. - `Sum.inr true` represents our first dummy item 'y'. - `Sum.inr false` represents our second dummy item 'z'. -/
def SubsetSumToPartition.partitionWeight (w : U → ℕ) (T : ℕ) : U ⊕ Bool → ℕ
  | Sum.inl a => w a
  | Sum.inr true => 2 * (∑ a, w a) - T
  | Sum.inr false => (∑ a, w a) + T
See it in the graphDiscuss this resultChallenge it