subset_sum_to_partition_equivalence
Let 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 solution if and only if the augmented Partition instance with weight function SubsetSumToPartition.partitionWeight w T has a solution.
Statement
theorem subset_sum_to_partition_equivalence {U : Type*} [Fintype U] [DecidableEq U] (w : U → ℕ) (T : ℕ) (h : T ≤ ∑ a, w a) : SubsetSumToPartition.SubsetSum w T ↔ SubsetSumToPartition.Partition (SubsetSumToPartition.partitionWeight w T)
- Formalizes
- Karp (1972), 'Reducibility among Combinatorial Problems'; Garey & Johnson (1979)
- Verified
- 14 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- 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…
- SubsetSumToPartition.partitionWeightThe weight function on the augmented universe $U \oplus \mathrm{Bool}$ built from a Subset Sum instance $(w, T)$. Writing…
- SubsetSumToPartition.SubsetSumGiven 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…
- SubsetSumToPartition.PartitionGiven 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…
Read back from the Lean
For any type U equipped with Fintype U and DecidableEq U, any weight function w : U → ℕ, any target T : ℕ, and any proof h that T ≤ ∑ a : U, w a (the sum over all elements of U), SubsetSumToPartition.SubsetSum w T holds if and only if SubsetSumToPartition.Partition (SubsetSumToPartition.partitionWeight w T) holds.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem establishes the correctness of Karp's reduction from Subset Sum to Partition under the target bound T ≤ ∑ a, w a. The proof packages the equivalence directly from two auxiliary theorems: completeness, which shows that any valid subset summing to T yields a balanced partition in the augmented instance, and soundness, which reconstructs a subset summing to T from any balanced partition.
The Subset Sum instance has a solution if and only if the augmented Partition instance has a solution.
The logical equivalence (↔) is established by pairing its two directions. The forward direction (completeness) is given by SubsetSumToPartitionCompleteness, which asserts that any subset with sum T induces an equal-weight bipartition in the augmented instance. The reverse direction (soundness) is given by SubsetSumToPartitionSoundness, which extracts a subset with sum T from any equal-weight bipartition of the augmented instance.
uses
SubsetSumToPartition.SubsetSumToPartitionCompleteness,SubsetSumToPartition.SubsetSumToPartitionSoundnessSubsetSumToPartition.Partition (SubsetSumToPartition.partitionWeight w T) := ⟨SubsetSumToPartition.SubsetSumToPartitionCompleteness w T h, SubsetSumToPartition.SubsetSumToPartitionSoundness w T h⟩
SubsetSumToPartition.SubsetSumToPartitionCompleteness- If a weight function w on a finite type has a subset summing to T (with T ≤ ∑ a, w a), then the augmented instance partitionWeight w T admits a balanced bipartition.
SubsetSumToPartition.SubsetSumToPartitionSoundness- If the augmented instance partitionWeight w T admits a balanced bipartition (with T ≤ ∑ a, w a), then the original instance has a subset summing to T.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- Correctness of the Subset Sum to Partition reduction under the target bound T ≤ ∑ a, w a. -/theorem subset_sum_to_partition_equivalence {U : Type*} [Fintype U] [DecidableEq U] (w : U → ℕ) (T : ℕ) (h : T ≤ ∑ a, w a) : SubsetSumToPartition.SubsetSum w T ↔ SubsetSumToPartition.Partition (SubsetSumToPartition.partitionWeight w T) := ⟨SubsetSumToPartition.SubsetSumToPartitionCompleteness w T h, SubsetSumToPartition.SubsetSumToPartitionSoundness w T h⟩