Subset-Sum NP Complete

Summary

We prove that the Subset-Sum problem is NP-Complete by reducing from 3SAT to SS.

Contents

• Subset Sum
  • SS is in NP
  • Reduce 3SAT to Subset-Sum
    • Variables
    • Example
  • Correctness
    • Forward Claim
    • Reverse Claim

Subset Sum

Input: positive integers $a_1, \ldots, a_n & t$

Output: Subet of numbers S that add up to t

If there is an O(nt) algorithm, this problem is NOT in P since its not polynomial in the SIZE of the input. It would need to be O(n log(t)).

SS is in NP

Given inputs $a_1, \ldots, a_n & t$ and S, check that $\displaystyle\sum_{i \in S} a_i = t$, takes time O(n log(t))

Reduce 3SAT to Subset-Sum

Input to subset-sum problem will be 2n + 2m + 1 numbers

$\begin{gathered} x_1 &\rightarrow v_1, \ \bar{x_1} &\rightarrow v_1', \ \vdots \ x_n &\rightarrow v_n, \ \bar{x_n} &\rightarrow v_n', \ s_1, \ s_1', \ \vdots \ s_m, \ s_m', \ t \end{gathered}$

All are $\le n + m$ digits long

$t \approx 10^{n+m}$

Variables

$v_i \hat{=} x_i : v_i \in S \iff x_i = T$

$v_i' \hat{=} \bar{x_i} : v_i' \in S \iff x_i = F$

Need to ensure exactly one of $v_i \lor v_i' \in S$

In ith digit of $v_i, v_i', & t$ put a 1, all other numbers put a 0

Example

$f = \left( \bar{x_1} \lor \bar{x_2} \lor \bar{x_3} \right) \land \left( \bar{x_1} \lor \bar{x_2} \lor x_3 \right) \land \left( x_1 \lor \bar{x_2} \lor x_3 \right) \land \left( x_1 \lor x_2 \right)$

This corresponds to only including $v_1 \lor v_1'$ since the sum has to equal the target of 1. Then digit n+j corresponds to clause $c_j$

if $x_i \in c_j$ put a 1 in digit n+j for $v_i$

This corresponds to only letting us pick 3 in the column of $c_1$. If all three are satisfied, we pick one of the $v_i$ variables. If one is not, we skip it and include one of the s variables (buffer). Since we only have 2 buffers but need a sum of 3, we have to have at least on literal be satisfied.

Correctness

SS has a solution $\iff$ 3SAT is satisfiable

Forward Claim

Take solution S to subset-sum

for digit i where $1 \le i \le n$:

• to get a 1 in digit i, include $v_i \lor v_i'$ but not both
  • $v_i \in S \implies x_i = T$
  • $v_i' \in S \implies x_i = F$

This gives us an assignment.

For digits n+j where $1 \le j \le m$:

• to get a sum of 3 in digit n+j, need to include $\ge 1$ literal of $c_j$

This proves our assignment is satisfying. $\blacksquare$

Reverse Claim

Take a satisfying assignment for f:

• $x_i = T \implies v_i \in S$
• $x_i = F \implies v_i' \in S$
  • ith digit of t is correct
• for clauses $c_j : \ge 1$ literals is satisfied
  • gets up to a sum of 3 in digit n+j, when using s buffers $\blacksquare$