You and a friend have been trekking through various far-off parts of the world and have ac...

You and a friend have been trekking through various far-off parts of the world and have accumulated a big pile of souvenirs. At the time you weren t really thinking about which of these you were planning to keep and which your friend was going to keep, but now the time has come to divide everything up.

Here's a way you could go about doing this. Suppose there are n objects, labeled 1,2,n, and object i has an agreed-upon value xi. (We could think of this, for example, as a monetary resale value; the case in which you and your friend don t agree on the value is something we won t pursue here.) One reasonable way to divide things would be to look for a partition of the objects into two sets, so that the total value of the objects in each set is the same.

This suggests solving the following Number Partitioning Problem. You are given positive integers x1,...,xn; you want to decide whether the numbers can be partitioned into two sets S1 and S2 with the same sum:

Show that Number Partitioning is NP-complete.