We will illustrate the construction using the example in
Figure 1. We will have numbers
corresponding to the logic variables with
corresponding to being included in the subset.
We will also need additional , for technical reasons.
The subset-sum problem is shown in Figure 2.
For clarity, we have divided the numbers into zones. will be a
sum of a
subset of the if and only if the totals within each zone
are appropriate.
Each zone corresponds to one of the logic formulas.
For through , the value in a zone is 0 if the corresponding
does not appear in the logic formula. If does appear,
a power of 2 is used. (the reason for using powers of 2 is that
different subsets of
will have different totals)
The leftmost zone corresponds to the first logic formula in
our example:
. By making suitable
decisions about inclusion of or , we will be able to get
a total of 4 in this zone, unless both and are left
out of the set, which is precisely what would make the logic formula
have value F.
The second zone corresponds to
, which has
value T unless is in the set and is not. ,
, and can be used to get the total for the zone
equal to 4 in any other case.
Similarly, each of the other zones^{5} has associated with
it which can be used to obtain the correct total except in one case.
The general problem is that we want numbers which can be used to
obtain any total between 1 and , except for one ``forbidden
total'' . [In the two zones discussed above is 4 in one
case and 3 in the other] We start with the powers of 2 from 1 to
. If
, replace by the two numbers
and .
[We did not follow exactly the procedure described in this paragraph
in constructing Figure 2.]