SubsetSumToPartition.Partition
defimported Lean
Given a weight function $v : U \to \mathbb{N}$ on a finite type $U$, the predicate asserts that some subset $S \subseteq U$ has the same total weight as its complement, i.e.\ $\exists S,\ \sum_{b \in S} v(b) = \sum_{b \in S^{c}} v(b)$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {U : Type*} [Fintype U] [DecidableEq U] in noncomputable def SubsetSumToPartition.Partition (v : U → ℕ) : Prop
- Defined in
- TCSlib, `SubsetSumToPartition.Partition`
- 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.Partition← SubsetSumToPartition.Partition (TCSlib/Complexity/NPReductions/SubsetSumToPartition.lean:76): 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 Partition problem: Given a finite set `U` and a weight function `v`, does there exist a subset `S` whose sum equals the sum of its complement `Sᶜ`? -/ noncomputable def SubsetSumToPartition.Partition (v : U → ℕ) : Prop := ∃ S : Finset U, (∑ b ∈ S, v b) = (∑ b ∈ Sᶜ, v b)