Next: Cook's Theorem Up: Subset-Sum Problems and NP-Completeness Previous: Converting (SP) to (SSP)   Contents

## Converting (SSP) to (SP)

Suppose we have a subset-sum problem with 50 , all between 1 and , with . Solving the SSP may be crudely broken into two steps:
1. Decide which are in the subset.
2. Verify that the sum of the chosen is .
Our (SP) will also carry out these steps. The first is simple: we will have logic variables with corresponding to being in the subset. To carry out the second step, we need to construct a set of logic formulas which acts as an adding machine'' to check the total.

We will represent numbers in base 2. Since all relevant numbers are , numbers may be represented by 26 logical variables. For each , we will have variables . These will represent if , 0 if . To do this, we need formulas which show how the value of determines the value of all the :

with the simple formula if the th digit of is 0.

Next, we need, for , variables which represent the total of the first of the numbers given by the -variables. Formulas are needed which show the -variables determining the -variables.

We begin with a set of formulas which have get value T if and only if an odd number of have value T. gets value T if and only if 2 or 3 of have value T:

If represent three one-digit numbers (0 or 1), the formulas have the effect that is the number in the column with the three numbers, while shows whether there is a number carried into the next column.

We will use ,...,, , to keep track of numbers being carried. Since there are no numbers carried in the rightmost column, we have the formulas . The formulas

have the effect of making represent the sum of the numbers and . To have represent the sum of and , we use

These logic formulas together have the effect that the determine the , which determine through successively. This last group of variables corresponds to the base-2 representation of the sum of the which are in the set we have chosen. Finally, we add the formulas or depending on whether the th digit of is 1 or 0. As planned, a solution to this satisfiability problem gives a solution to the subset-sum problem (look at which have value T), which implies that a method of solving (SP) can be used to solve (SSP).

The (SP) we have constructed is rather large, involving approximately formulas. However, the rate of growth if we had more with a larger upper limit is not too bad.

Next: Cook's Theorem Up: Subset-Sum Problems and NP-Completeness Previous: Converting (SP) to (SSP)   Contents
Translated from LaTeX by Scott Sutherland
2002-12-14