SubsetSumToPartition.SubsetSum
defimported Lean
Given a weight function $w : U \to \mathbb{N}$ on a finite type $U$ and a target $T \in \mathbb{N}$, the predicate asserts that some subset $S \subseteq U$ has total weight exactly $T$, i.e.\ $\exists S,\ \sum_{a \in S} w(a) = T$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {U : Type*} [Fintype U] [DecidableEq U] in noncomputable def SubsetSumToPartition.SubsetSum (w : U → ℕ) (T : ℕ) : Prop
- Defined in
- TCSlib, `SubsetSumToPartition.SubsetSum`
- 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.SubsetSum← SubsetSumToPartition.SubsetSum (TCSlib/Complexity/NPReductions/SubsetSumToPartition.lean:69): 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 /-- The Subset Sum problem: Given a weight function `w` and a target `T`, does there exist a subset `S` of `U` whose weights sum exactly to `T`? -/ noncomputable def SubsetSumToPartition.SubsetSum (w : U → ℕ) (T : ℕ) : Prop := ∃ S : Finset U, (∑ a ∈ S, w a) = T