In this post, we will prove that the set-partition problem is NP-complete using a reduction from the subset sum problem (which is NP-complete[1]). This is Exercise 34.5-5 in CLRS3[1]. We will follow the template given in an earlier post.
Problem statement
Given a set of numbers, determine whether
can be partitioned into
and
, such that:
(1)
Showing the problem is in NP
Let be the certificate. We can verify the certificate in linear time by summing the elements in each set, and comparing it
Showing the problem is NP-hard
We will show that the set-partition problem is NP-hard by showing:
(2)
Reduction
We will prove that the existence of with sum
can be partitioned into
as described by the set-partition problem (
being the sum of
). We note that
can be constructed in
by first summing the elements in
and then adding
to S, which proves our reduction is performed in polynomial time.
We will now prove both directions of the biconditional separately.
the set-partition problem on
has a solution
Suppose exists. Let
be
, i.e the “out”-elements. Let
be the sum of
. Let
and
be the sum of
. We can now make the following observations:
(3)
This proves:
(4)
The set-partition problem on
has a solution 
Suppose an equal-sum partitioning of
exists. The sum
of each partition must then be
. We consider the partition containing the element
to be
. Let
. We can observe
. The sum of
is
. In other words:
is a subset of
with sum
, i.e. a witness to
- [1]T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT Press, 2009.