AFTD Auto-Formalizing Theoretical Domains

subset_sum_to_partition_equivalence

theoremverifiedformalization

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

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.

  1. 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.

    lines 5–6

    uses SubsetSumToPartition.SubsetSumToPartitionCompleteness, SubsetSumToPartition.SubsetSumToPartitionSoundness

          SubsetSumToPartition.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⟩
See it in the graphDiscuss this resultChallenge it