Converting (SP) to (SSP)

We want to construct numbers $a_i$ and a target number $T$ so that there is a subset adding up to $T$ if and only if there is an assignment for (SP) which makes all the formulas true. Using this construction allows us to use an algorithm for (SSP) to solve (SP). It implies that solving (SSP) is at least as hard as solving (SP).

We will illustrate the construction using the example in Figure 1. We will have numbers $a_1,\dots,a_5$corresponding to the logic variables $A_1,\dots,A_5$ with $A_i={\bf T}$ corresponding to $a_i$ being included in the subset. We will also need additional $a_i$, $i>5$ for technical reasons.

  

Figure 2: Subset-sum problem

The subset-sum problem is shown in Figure 2. For clarity, we have divided the numbers into zones. $T$ will be a sum of a subset of the $a_i$ if and only if the totals within each zone are appropriate. Each zone corresponds to one of the logic formulas. For $a_1$ through $a_5$, the value in a zone is 0 if the corresponding $A_i$ does not appear in the logic formula. If $A_i$ does appear, a power of 2 is used. (the reason for using powers of 2 is that different subsets of $\{a_1,\dots,a_5\}$ will have different totals)

The leftmost zone corresponds to the first logic formula in our example: $A_1\hbox{ or }A_2$. By making suitable decisions about inclusion of $a_6$ or $a_7$, we will be able to get a total of 4 in this zone, unless both $a_1$ and $a_2$ are left out of the set, which is precisely what would make the logic formula have value F.

The second zone corresponds to $\sim A_1\hbox{ or }A_5$, which has value T unless $a_1$ is in the set and $a_5$ is not. $a_8$, $a_9$, and $a_{10}$ can be used to get the total for the zone equal to 4 in any other case.

Similarly, each of the other zones⁵ has $a_i$ 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 $2^n$, except for one ``forbidden total'' $M$. [In the two zones discussed above $M$ is 4 in one case and 3 in the other] We start with the powers of 2 from 1 to $2^n$. If $2^j\le M<2^{j+1}$, replace $2^j$ by the two numbers $M-2^j$ and $M+1$. [We did not follow exactly the procedure described in this paragraph in constructing Figure 2.]

Footnotes

... zones⁵

We have omitted the $a_i$ for the last three zones in Figure 2.