Is the set partitioning problem NP-complete?
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.