SUBSET-SUM is NP-complete

Given a collection of numbers  and a target number . To determine whether the collection contains a subcollection that adds up to .

SUBSET-SUM is in NP

 " On input :

1. Test whether  is a collection of numbers that sum to .
2. Test whether  contains all the numbers in .
3. If both pass, accept; otherwise, reject."

SUBSET-SUM is NP-complete

Recall that the formulas in 3SAT are in conjunctive normal form (cnf) with three literals per clause.

Let  be a Boolean formula with variables  and clauses  The reduction converts  to an instance of the  problem  wherein the elements of  and the number  are the rows in the table in figure below expressed in ordinary decimal notation. The rows above the double line are labeled

and constitute the elements of  The row below the double line is .

Thus,  contains one pair of numbers,  for each variable  in  The decimal representation of these numbers is in two parts, as indicated in the table. The left-hand part comprises a 1 followed by  0s. The right-hand part contains one digit for each clause, where the digit of  in column  is 1 if clause  contains literal , and the digit of  in column  is 1 if clause  contains literal  Digits not specified to be 1 are 0 . The table is partially filled in to illustrate sample clauses,  and 

Additionally,  contains one pair of numbers,  for each clause  These two numbers are equal and consist of a 1 followed by  0s.

Finally, the target number  the bottom row of the table, consists of s followed by  3s.

Next, we show why this construction works. We demonstrate that  is satisfiable iff some subset of  sums to .

Suppose that  is satisfiable. We construct a subset of  as follows. We select  if  is assigned TRUE in the satisfying assignment, and  if  is assigned FALSE. If we add up what we have selected so far, we obtain a 1 in each of the first  digits because we have selected either  or  for each  Furthermore, each of the last  digits is a number between 1 and 3 because each clause is satisfied and so contains between 1 and 3 true literals. We additionally select enough of the  and  numbers to bring each of the last  digits up to  thus hitting the target.

Suppose that a subset of  sums to  We construct a satisfying assignment to  after making several observations. First, all the digits in members of  are either 0 or  Furthermore, each column in the table describing  contains at most five 1 s. Hence a "carry" into the next column never occurs when a subset of  is added. To get a 1 in each of the first  columns, the subset must have either  or  for each  but not both.

Now we make the satisfying assignment. If the subset contains  we assign  TRUE; otherwise, we assign it FALSE. This assignment must satisfy  because in each of the final  columns, the sum is always  In column at most 2 can come from  and  so at least 1 in this column must come from some  or  in the subset. If it is  then  appears in  and is assigned  so  is satisfied. If it is  then  appears in  and  is assigned FALSE, so  is satisfied. Therefore,  is satisfied.

Finally, we must be sure that the reduction can be carried out in polynomial time. The table has a size of roughly  and each entry can be easily calculated for any  So the total time is  easy stages.