HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is the set-partition problem polynomial time reducible to the subset-sum problem?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemthepartitionpolynomialreducibletimesumsubsetset

Problem

There are many solutions on the web showing that the subset-sum problem is polynomial time reducible to the set-partition problem. However, during my search, I came across the following powerpoint presentation (slide 12), where it says that the inverse is also true. i.e. the set-partition problem is polynomial time reducible to the subset-sum problem.
So far, I have been unable to find any proofs to show the same.

So, my question: How is the set-partition problem polynomial time reducible to the subset-sum problem, or was there an error on the presentation above?

Solution

First, both problems are NP-complete, and are therefore reducible to each other. A concrete reduction can go through the Cook-Levin theorem (i.e. SET-PARTITION$\le_p$SAT$\le_p$SUBSET-SUM).

However, in this case there is a fairly trivial direct reduction: given an instance $\{x_1,...,x_n\}$ for SET-PARTITION, compute $t=\sum_{i=1}^n x_i$ and output $\{x_1,...,x_n\},t/2$ as input for SUBSET-SUM. The correctness of this is very easy to show.

Context

StackExchange Computer Science Q#18159, answer score: 3

Revisions (0)

No revisions yet.