3-SAT to Subset Sum (Karp Reduction)

Definition

3-SAT to Subset Sum

There is a polynomial-time many-one reduction from the 3-SAT problem to the Subset Sum problem:

$$3\text{-}\mathrm{SAT}{\le }_m^p\mathrm{SUBSET}\mathrm{SUM}.$$

Construction

Let

$$F=C_1\wedge \cdots \wedge C_m$$

be a 3-SAT formula over variables $x_1,\dots ,x_n$. Represent each constructed integer by $n+m$ decimal digits, divided into

$$\underset{\text{variable digits}}{\underbrace{x_1\cdots x_n}}|\underset{\text{clause digits}}{\underbrace{C_1\cdots C_m}}.$$

For a predicate $P$, write $[P]=1$ when $P$ is true and $[P]=0$ otherwise.

Assignment numbers

For every variable $x_i$, create two numbers $t_i$ and $f_i$. Their variable digits satisfy

$$(t_i{)}_r=(f_i{)}_r=[r=i](1\le r\le n).$$

Their clause digits record which clauses the corresponding assignment satisfies:

$$(t_i{)}_{n+j}=[x_i\in C_j],(f_i{)}_{n+j}=[\neg x_i\in C_j].$$

Selecting $t_i$ represents $x_i=\top$; selecting $f_i$ represents $x_i=\perp$.

The following table shows the construction for

$$F=(x_1\vee x_2\vee \neg x_3)\wedge (\neg x_1\vee x_2\vee x_3).$$

Each pair has its $1$ in the same variable column. The clause columns differ according to which choice makes each clause true.

Fill-up numbers

For each clause $C_j$, create two distinct copies $p_j$ and $q_j$ of the number whose only non-zero digit is a $1$ in clause position $C_j$. These numbers can add zero, one, or two to that clause digit.

The target $3$ leaves exactly enough room to fill every positive contribution, but not a zero contribution:

Target

Set the target to

$$W=\underset{n\text{ variable digits}}{\underbrace{11\cdots 1}}|\underset{m\text{ clause digits}}{\underbrace{33\cdots 3}}.$$

The resulting Subset Sum multiset is

$$A=\{t_i,f_i:1\le i\le n\}\cup \{p_j,q_j:1\le j\le m\}.$$

No-carry Invariant

Decimal addition is digitwise

No selected subset can produce a carry. A variable digit receives at most two units, one from $t_i$ and one from $f_i$. A clause digit receives at most three units from assignment numbers and two from its fill-up numbers. Every digit sum is therefore at most $5<10$.

Consequently, equality with $W$ can be checked independently in every digit position.

Correctness

The formula $F$ is satisfiable if and only if some submultiset of $A$ sums exactly to $W$.

Correctness

Forward

Suppose that an assignment satisfies $F$. For each variable $x_i$, select $t_i$ if $x_i=\top$ and $f_i$ if $x_i=\perp$. Every variable digit then sums to exactly $1$.

In each clause digit, the selected assignment numbers contribute $r\in \{1,2,3\}$ because the clause has at least one true literal. Select exactly $3-r$ of the clause’s two fill-up numbers. Every clause digit then reaches $3$, so the selected numbers sum to $W$.

Backward

Suppose that a submultiset of $A$ sums to $W$. Since the variable digit for $x_i$ has target $1$, the no-carry invariant forces the subset to contain exactly one of $t_i$ and $f_i$. These choices define a truth assignment.

Consider a clause digit. Its two fill-up numbers can contribute at most $2$, while its target is $3$. At least one selected assignment number must therefore contribute $1$ to this digit. By construction, its chosen truth value satisfies a literal of the clause. Hence every clause is satisfied.

Running Time

The reduction creates $2n+2m$ integers, each with $n+m$ decimal digits. Its output contains

$$O((n+m{)}^2)$$

digits in total. Since an $(n+m)$-digit decimal integer also has $O(n+m)$ binary bits, the reduction runs in time polynomial in the size of the 3-SAT instance.

Numerical Magnitude

The constructed integers may have numerical value as large as $10^{n+m}$. Their values are therefore exponential even though their binary encodings have polynomial length. This reduction proves NP-hardness but does not establish strong NP-hardness, consistently with Subset Sum being weakly NP-hard.

NP-completeness

Since 3-SAT is NP-hard, the reduction proves that Subset Sum is NP-hard. Together with membership in NP, this proves that Subset Sum is NP-complete.

Example

Two clauses

Consider

$$F=(x_1\vee x_2\vee \neg x_3)\wedge (\neg x_1\vee x_2\vee x_3).$$

Use the digit order $x_1{x}_2{x}_3\mid C_1{C}_2$. The construction gives:

number	digits	satisfied clauses
$t_1$	100 10	$C_1$
$f_1$	100 01	$C_2$
$t_2$	010 11	$C_1,C_2$
$f_2$	010 00	none
$t_3$	001 01	$C_2$
$f_3$	001 10	$C_1$
$p_1,q_1$	000 10	fill $C_1$
$p_2,q_2$	000 01	fill $C_2$
$W$	111 33	target

Under the satisfying assignment $x_1=\perp$, $x_2=\top$, and $x_3=\perp$, select $f_1,t_2,f_3$. Their sum is 111 22. Adding one fill-up number for each clause reaches 111 33: