[Rule] KSatisfiability to SubsetSum

[zazabap]

Source: KSatisfiability (3-SAT)
Target: SubsetSum
Motivation: Classical Karp reduction bridging Boolean satisfiability (formula domain) to number theory (algebraic domain). The canonical proof that SubsetSum is NP-complete. Uses a base-10 digit encoding where each digit position is independent (no carries).
Reference: Karp, 1972; Sipser, Introduction to the Theory of Computation, 2012, Theorem 7.56; CLRS, 4th ed., 2022, §34.5.5

Reduction Algorithm

Notation:

• Source: 3-CNF formula $\phi$ with $n$ variables $x_1, \ldots, x_n$ and $m$ clauses $C_1, \ldots, C_m$
• Target: SubsetSum instance with set $S$ of $2n + 2m$ integers and target $T$, each integer having $(n + m)$ decimal digits

Step 1 — Variable integers ($2n$ integers):

For each variable $x_i$, create two integers using $(n+m)$-digit base-10 representation:

$$y_i: \quad d_i = 1, \quad d_{n+j} = 1 \text{ if } x_i \in C_j$$ $$z_i: \quad d_i = 1, \quad d_{n+j} = 1 \text{ if } \overline{x_i} \in C_j$$

where $d_k$ denotes the $k$-th digit (1-indexed, most significant first).

Step 2 — Slack integers ($2m$ integers):

For each clause $C_j$, create two slack integers:

$$g_j: \quad d_{n+j} = 1 \quad \text{(all other digits 0)}$$ $$h_j: \quad d_{n+j} = 2 \quad \text{(all other digits 0)}$$

Step 3 — Target:

$$T: \quad d_i = 1 ;\forall, i \in [1, n], \quad d_{n+j} = 4 ;\forall, j \in [1, m]$$

Why no carries: Each variable digit sums to exactly 1 (we pick $y_i$ or $z_i$). Each clause digit sums to at most $3$ (from literals) $+ 2$ (from $h_j$) $= 5 < 10$, so digits are independent.

Why it works: Selecting $y_i$ ($z_i$) corresponds to setting $x_i = T$ ($x_i = F$). Variable digits force exactly one of $y_i, z_i$ per variable. Clause digits count how many selected literals satisfy each clause; the slacks $g_j, h_j$ pad to exactly 4, which is possible iff at least 1 literal satisfies the clause (contribution 1–3, padded with slack 1–3).

Solution extraction: For each $i$: if $y_i$ is in the subset, set $x_i = 1$; if $z_i$ is in the subset, set $x_i = 0$.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_elements	$2n + 2m$
max_digits	$n + m$

Validation Method

Closed-loop testing: solve 3-SAT by brute-force ($2^n$ enumeration), solve the reduced SubsetSum by brute-force ($2^{2n+2m}$ enumeration), and verify that the formula is satisfiable iff the target sum is achievable. Test with: satisfiable instance, unsatisfiable instance, single-clause, single-variable.

Example

Source instance: 3-SAT formula $(x_1 \lor x_2 \lor x_3) \land (\overline{x_1} \lor \overline{x_2} \lor x_3)$, $n = 3$, $m = 2$.

Constructed integers (5-digit base-10):

Integer	$d_1$	$d_2$	$d_3$	$d_4$ (C₁)	$d_5$ (C₂)	Decimal
$y_1$	1	0	0	1	0	10010
$z_1$	1	0	0	0	1	10001
$y_2$	0	1	0	1	0	1010
$z_2$	0	1	0	0	1	1001
$y_3$	0	0	1	1	1	111
$z_3$	0	0	1	0	0	100
$g_1$	0	0	0	1	0	10
$h_1$	0	0	0	2	0	20
$g_2$	0	0	0	0	1	1
$h_2$	0	0	0	0	2	2

Target: $T = 11144$

Verification: Assignment $x_1 = T, x_2 = T, x_3 = T$ (satisfying):

• Select $y_1 + y_2 + y_3 = 10010 + 1010 + 111 = 11131$
• Clause digits: $C_1 = 3, C_2 = 1$. Need $+1$ for $C_1$, $+3$ for $C_2$
• Add $g_1 + h_2 + g_2 = 10 + 2 + 1 = 13$
• Total: $11131 + 13 = 11144 = T$ ✓

Assignment $x_1 = F, x_2 = F, x_3 = F$ (unsatisfying — clause 1 has 0 true literals):

• Select $z_1 + z_2 + z_3 = 10001 + 1001 + 100 = 11102$
• Clause digits: $C_1 = 0, C_2 = 2$. Need $+4$ for $C_1$ — but max slack is $g_1 + h_1 = 3$. Cannot reach 4. ✗