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!
Karmarkar and Karp do not claim that the second problem is NP-complete.  It can't be, because it is not in NP. Remember that NP is a class of decision problems, i.e., problems where the answer is either "yes" or "no".  Because the problem is not in NP, it's not required that the answer be efficiently checkable.  The same thing happens with TSP: sure, if I give you a route around the cities and claim that it's less than 50 miles, you can check that easily; but if I give you a route and claim that it's the shortest, there's (probably) no way to check that in polynomial time.

Rather, the second problem is what is known as an NP optimization problem. It asks us to minimize a certain function&nbsp;$f$ and the decision problem, "Given $S$ and&nbsp;$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.