Difficulty: Intermediate to Advanced | Prerequisites: NP, polynomial-time verifiers, polynomial-time reductions, SUBSET-SUM (known NP-Complete).
This covers a chain of NP-Completeness proofs that connect number-partitioning problems. PARTITION asks whether a set of integers can be split into two subsets of equal sum. BIN-PACKING asks whether items of given sizes can fit into a limited number of fixed-capacity bins. Both are proved NP-Complete through reductions from previously known NP-Complete problems (SUBSET-SUM ≤p PARTITION ≤p BIN-PACKING), building the web of hardness results that underpins complexity theory. You also see the search-from-decision technique again, applied to PARTITION.
PARTITION is NP-Complete because you can reduce SUBSET-SUM to it by adding one carefully chosen extra element that forces a partition to exist if and only if a target-sum subset exists. BIN-PACKING is NP-Complete because PARTITION reduces to it by setting the bin capacity to half the total sum and asking for two bins. A black-box PARTITION decider can find the actual partition by merging elements and testing whether the set remains partitionable.
PARTITION
The decision problem: given a set S of integers, can S be divided into two disjoint subsets A and B such that A ∪ B = S, A ∩ B = ∅, and the sum of elements in A equals the sum of elements in B? In simple terms, can you split a pile of numbers into two piles that weigh the same?
SUBSET-SUM
Given a set S and a target value k, does there exist a subset S* ⊆ S whose elements sum to exactly k? Think of it as: can you pick some numbers from the pile that add up to a specific target?
BIN-PACKING
Given a bin capacity v, a set A of n item sizes, and an integer b, can all n items be packed into at most b bins, where no bin exceeds capacity v? In simple terms, can you fit all your stuff into a limited number of boxes of the same size?
Verifier (V)
A polynomial-time algorithm that takes an input and a certificate, and accepts if the certificate proves the input is a yes-instance. Constructing an efficient verifier is how you show a problem is in NP.
Certificate
The "proof" or "witness" that a verifier checks. For PARTITION, the certificate is the two subsets A and B. For BIN-PACKING, it is the assignment of items to bins.
Certificate: two sets A and B that claim to partition S.
Verifier V on input ⟨S⟩, (A, B):
If A ∪ B ≠ S, reject.
If A ∩ B ≠ ∅, reject.
If Σ(A) ≠ Σ(B), reject.
Accept.
Runtime: Step 1 is O(|S|), Step 2 is O(|S|²), Step 3 is O(|S|), Step 4 is O(1). All polynomial.
Correctness: if S ∈ PARTITION, a valid partition exists and will pass all checks. If S ∉ PARTITION, no certificate passes Step 3 (or fails Steps 1/2).
The reduction function f:
On input (S, k):
Compute s = sum of all elements in S.
If s ≥ 2k, set S' = S ∪ {s - 2k}. If s < 2k, set S' = S ∪ {2k - s}.
Return S'.
The idea: you add one extra number that forces the total sum of S' to be exactly 2k (when s ≥ 2k, the new total is s + (s - 2k) = 2s - 2k, and each partition half sums to s - k) or exactly 2k (when s < 2k, the new total is s + (2k - s) = 2k, and each partition half sums to k).
Why f is valid:
Polynomial time: Step 1 is O(|S|), Steps 2-3 are O(1).
Forward direction (s ≥ 2k case): (S, k) ∈ SUBSET-SUM means some subset X ⊆ S sums to k. The remaining elements S \ X sum to s - k. Partition S' as: one set = S \ X (sums to s - k), other set = X ∪ {s - 2k} (sums to k + s - 2k = s - k). Both halves equal s - k, so S' ∈ PARTITION.
Forward direction (s < 2k case): Subset X sums to k. Partition S' as: one set = X (sums to k), other set = (S \ X) ∪ {2k - s} (sums to (s - k) + (2k - s) = k). Both halves equal k, so S' ∈ PARTITION.
Backward direction (s ≥ 2k case): S' ∈ PARTITION means S' splits into two equal-sum halves. The added element s - 2k must be in one half. Removing it from that half gives a set summing to (s - k) - (s - 2k) = k. That set is a subset of S summing to k, so (S, k) ∈ SUBSET-SUM.
Backward direction (s < 2k case): Similarly, if each half sums to k, one half that does not contain the added element 2k - s is a subset of S summing to k.
Certificate: a set of arrays C where each array represents a bin and lists the item indices assigned to it.
Verifier V on input (⟨v, A, b⟩, C):
If |C| > b, reject.
Initialise an assignment tracker I of size n, all zeros.
For each bin Bi in C: sum the sizes of its items and check that the total does not exceed v. Also increment I[j] for each item j in the bin.
If any entry in I is not exactly 1, reject (some item is unassigned or double-assigned).
Accept.
Runtime: O(|A|²) overall. All steps polynomial.
The reduction function f:
On input ⟨S⟩:
Set v = (1/2) × Σ S (half the total sum).
Set A = S (the item sizes are the set elements).
Set b = 2.
Return ⟨v, A, b⟩.
The idea: a set S can be partitioned into two equal-sum halves if and only if all items (with sizes equal to the set elements) can be packed into exactly 2 bins of capacity (total sum)/2.
Why f is valid:
Polynomial time: computing the sum is O(|S|), everything else is O(1).
Forward: S ∈ PARTITION means subsets A, B exist with equal sums. Each sum equals v. Pack A's elements in bin 1, B's in bin 2. Both fit within capacity v. So f(S) ∈ BIN-PACKING.
Backward: f(S) ∈ BIN-PACKING means all items fit in 2 bins of capacity v. The items in each bin form a subset of S, the two subsets are disjoint, they cover S, and each subset's sum is at most v. Since the total is 2v, each must sum to exactly v. So S ∈ PARTITION.
Given a black-box decider D for PARTITION, find the actual two subsets (or report "NO PARTITION").
Algorithm:
On input S = [s₁, ..., sₙ]:
Run D on S. If it rejects, return "NO PARTITION."
Define A = {s₁} and B = {s₂, ..., sₙ}.
Initialise an empty set P (tracks tested elements).
While Sum(A) ≠ Sum(B):
Pick an element e ∈ B not yet in P.
Add e to P.
Construct S' = S \ (A ∪ {e}) ∪ {Sum(A) + e}. (Replace all elements of A and e with their combined sum.)
Run D on S'.
If D accepts: move e from B to A (e belongs with A).
Return (A, B).
The core idea:
To test whether element e belongs in the same partition as the elements already in A, you replace all of A's elements and e with a single number equal to their sum. If the modified set is still partitionable, it means those numbers can all be in the same subset (their individual values do not matter, only their total). If D rejects, e must be in the other subset.
Worked example with S = [2, 3, 6, 11]:
The correct partition is A = {2, 3, 6}, B = {11}.
Start: A = {2}, B = {3, 6, 11}
Test e = 3: S' = {5, 6, 11} (merged 2 + 3 = 5). D accepts. Move 3 to A.
Test e = 11: S' = {6, 16} (merged 2 + 3 + 11 = 16). D rejects. Keep 11 in B.
Test e = 6: S' = {11, 11} (merged 2 + 3 + 6 = 11). D accepts. Move 6 to A.
Now Sum(A) = 11 = Sum(B). Return ({2, 3, 6}, {11}).
Efficiency:
The while loop runs at most O(|S|) times. Each iteration does O(|S|) work plus one call to D. Total: O(|S|) calls to D, each polynomial, so the whole algorithm is polynomial.
PARTITION language:
PARTITION = {⟨S⟩ : S can be partitioned into 2 disjoint subsets of equal respective sums}
SUBSET-SUM language:
SUBSET-SUM = {(S, k) : there exists S* ⊆ S such that Σ(S*) = k}
BIN-PACKING language:
BIN-PACKING = {⟨v, A, b⟩ : v is the capacity of each bin, A is the set of sizes for n items, and b is an integer where the n items can be packed using at most b bins}
SUBSET-SUM → PARTITION reduction:
f(S, k): let s = Σ(S). If s ≥ 2k, return S ∪ {s - 2k}. If s < 2k, return S ∪ {2k - s}.
PARTITION → BIN-PACKING reduction:
f(⟨S⟩) = ⟨v = (1/2)Σ(S), A = S, b = 2⟩
PARTITION models fair division problems: splitting assets in a divorce settlement, balancing workloads across two servers, or (as in the homework) dividing players into two equally skilled teams. BIN-PACKING appears in logistics (loading containers onto trucks), memory allocation (fitting processes into RAM pages), and cutting stock problems in manufacturing (cutting pieces from standard-sized raw material with minimal waste).
Students often forget that the SUBSET-SUM to PARTITION reduction must handle two cases (s ≥ 2k and s < 2k). Both cases are needed for the proof to be complete. The added element differs depending on which case applies.
Students sometimes think PARTITION requires the two subsets to have the same number of elements. It does not. Only the sums must be equal. The subsets can be different sizes.
When proving BIN-PACKING is NP-Complete, students occasionally try to reduce from a problem that is not already known to be NP-Hard. You must start from a known NP-Hard problem. Here the chain is: SUBSET-SUM (known NP-Hard) → PARTITION → BIN-PACKING.
In the search-from-decision algorithm for PARTITION, students sometimes misunderstand why merging elements works. The key insight is that replacing numbers with their sum preserves partitionability only if those numbers all belong to the same partition half.
⚠️ The SUBSET-SUM to PARTITION reduction is more intricate than most reductions in this course. Expect to be tested on the two-case structure and the reasoning behind the added element.
⚠️ The PARTITION to BIN-PACKING reduction is one of the simplest in the course. It sets b = 2 and v = half the total. Know it as a quick example of a clean reduction.
⚠️ Constructing verifiers is frequently tested. Remember the pattern: describe the certificate, write the verifier steps, prove polynomial runtime, and argue completeness (yes-instances have a valid certificate) and soundness (no-instances reject all certificates).
⚠️ The search-from-decision technique for PARTITION (merging elements) is a distinct pattern from the one used for CLIQUE (removing vertices). Be ready to explain or reproduce either.
True or False: PARTITION requires the two subsets to have the same number of elements. Answer: False. Only the sums must be equal.
Fill in the blank: In the SUBSET-SUM to PARTITION reduction, when s ≥ 2k, the element added to S is ______. Answer: s - 2k.
True or False: In the PARTITION to BIN-PACKING reduction, the number of bins b is set to |S|/2. Answer: False. b is set to 2 (two bins, one per partition half).
Fill in the blank: In the search-from-decision algorithm for PARTITION, if replacing elements of A and e with Sum(A) + e causes D to reject, this means e belongs in subset ______. Answer: B (the other subset, not with A).
True or False: BIN-PACKING ∈ NP because the verifier checks that items fit in bins and each item is assigned exactly once. Answer: True.
Q: In the SUBSET-SUM to PARTITION reduction, why is it necessary to handle the cases s ≥ 2k and s < 2k separately?
A: Because the added element must be non-negative (it is a member of a set of integers being partitioned). When s ≥ 2k, adding s - 2k is non-negative. When s < 2k, s - 2k would be negative, so instead you add 2k - s. The two cases ensure the reduction always produces a valid PARTITION instance.
Q: Describe the certificate and verifier for BIN-PACKING. What does each step of the verifier check?
A: The certificate is a collection of arrays C, one per bin, listing the items assigned to that bin. The verifier checks: (1) no more than b bins are used, (2) no bin's items exceed capacity v, and (3) every item is assigned to exactly one bin. All steps run in polynomial time.
Q: In the search-from-decision algorithm for PARTITION, what happens when you test element e = 11 with A = {2, 3} and S = [2, 3, 6, 11]?
A: You construct S' = {6, 16} by removing 2, 3, and 11 from S and adding 2 + 3 + 11 = 16. D rejects S' because {6, 16} cannot be partitioned into two equal-sum subsets (6 ≠ 16). This tells you 11 does not belong in the same partition as 2 and 3.
Q: Prove that the PARTITION to BIN-PACKING reduction is correct in the backward direction.
A: If f(S) = ⟨v, A, 2⟩ ∈ BIN-PACKING, all items fit into 2 bins of capacity v = (1/2)Σ(S). The two bins' contents form disjoint subsets covering S, each with sum at most v. Since the total sum is 2v, each bin must sum to exactly v. So S has two disjoint subsets of equal sum, meaning S ∈ PARTITION.
PARTITION and BIN-PACKING sit in a chain of reductions that includes SUBSET-SUM, which itself reduces from 3-SAT through intermediate problems. This illustrates how NP-Completeness proofs build on each other: each new proof adds a link to the chain.
The BIN-PACKING problem connects directly to approximation algorithms (covered in HW 8 Q3b), where the first-fit greedy algorithm provides a 2-approximation. This is significant because exact solutions are NP-Hard, so approximations are the practical alternative.
The search-from-decision pattern here (merging elements and testing partitionability) is conceptually distinct from the pattern used for CLIQUE (removing vertices). Both are worth knowing as templates.
Related Terms / Search Tags
partition problem, subset sum, bin packing, NP-Complete, NP-Hard, polynomial-time reduction, verifier, certificate, fair division, equal-sum partition, number partitioning, first-fit algorithm, search from decision, EECS 376, computational complexity, reduction chain