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.SubsetSumToPartition.partitionWeight← SubsetSumToPartition.partitionWeight (TCSlib/Complexity/NPReductions/SubsetSumToPartition.lean:87): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 3
- SubsetSumToPartition.SubsetSumToPartitionCompletenessCompleteness of the Subset Sum to Partition reduction. Let $w : U \to \bbn$ be a weight function on a finite type $U$, and let…
- subset_sum_to_partition_equivalenceLet w : U → ℕ be a weight function on a finite type U, and let T : ℕ satisfy T ≤ ∑ a, w a. Then the Subset Sum instance (w, T) has a…
- SubsetSumToPartition.SubsetSumToPartitionSoundnessSoundness of the Subset Sum to Partition reduction. Let $w : \bbn^{U}$ be a weight function on a finite type $U$, and let $T \in \bbn$ be…
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