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! 
Is the set partitioning problem NP-complete?
complexity theory;optimization;np complete;partitions