** 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:
- Decide which
are in the subset.
- 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