# Is the set partitioning problem NP-complete?

I know that the set partitioning problem defined like this:

Given $$S = \left\{ x_1, \ldots x_n \right\}$$ find $S_1$ and $S_2$ such that $S_1 \cap S_2 = \emptyset$, $S_1 \cup S_2 = S$ and $\displaystyle\sum_{x_i \in S_1} x_i=\sum_{x_i \in S_2} x_i.$

is NP-complete. But I don't understand why (or am not even sure if) the following problem is NP-complete:

Given $$S = \left\{ x_1, \ldots x_n \right\}$$ find $S_1$ and $S_2$ such that $S_1 \cap S_2 = \emptyset$, $S_1 \cup S_2 = S$ and $$| \sum_{x_i \in S_1} x_i-\sum_{x_i \in S_2} x_i |$$ is minimized.

The paper 'The Differencing Method of Set Partitioning' by Karp and Karmarkar and some others say that it is NP-complete. But, if I have a sample solution to this problem, I can not tell whether it is an optimal solution (unlike in the first problem) and therefore I feel it NP-hard. If this is not true, how can I conclude that it is NP-complete? Thanks!

• The second problem is in its optimization form. It can be converted to decision version by asking if discrepancy is less than or equal to $k$. HINT: what value of $k$ will give you the original problem? – Nicholas Mancuso Dec 9 '13 at 18:20
• @NicholasMancuso k=0 will give the original problem. But we don't know what k is to begin with. I understand that the decision version of the second problem is NP-complete. But shouldn't the problem be referred to as being NP-hard? Like for instance, the travelling salesman problem is NP-hard, whereas the decision version of TSP is NP-complete. – SashaGreen Dec 9 '13 at 18:36

Rather, the second problem is what is known as an NP optimization problem. It asks us to minimize a certain function $f$ and the decision problem, "Given $S$ and $k$, is $f(S)\leq k$?" is in NP. Now, if this decision problem is NP-complete, the optimization problem is NP-hard: there's a trivial reduction from the decision version to the optimization problem. Going the other way around, if you had an efficient algorithm for the decision problem, you could find out the optimum by binary search.