Reduce Subset-Sum to Sat

Question

Is there a reduction from SUBSET-SUM to SAT? Just general SAT, not 3-SAT. Also the given multiset S only has positive integers.

SUBSET-SUM is defined as follows: Input: a multiset S = { x1 , ... , xn } of positive integers and a positive integer t Output: accept if there exists a sub-multiset { y1, …, ym } ⊆ S such that y1 + ··· + ym = t reject otherwise

x1 , ... , xn and t are encoded in binary notation.

The boolean formula SUM should be used in the reduction.

Let a1···ak, b1···bk, c1···ck be k-bit integers.

SUM(a1, ... , ak, b1, ... , bk, c1, ... , ck) is true iff (a1···ak) + (b1···bk) = c1···ck

For example, if k = 3, sum(0, 1, 1, 1, 0, 0, 1, 1, 1) is true because 011 + 100 = 111.

Can this be done?

For example, what would the boolean formula produced by the reduction look like for S = { 010, 011, 011, 100 } t = 110

Answer 1

I think a direct reduction can be done by the following process: setup a enable gate $e_i$ for each integer $x_i$ (then we can represent each bit of $x_i$ using $e_i$ and $0$), add all integers (with enable gate) up using adder circuits, then compare the overall sum with goal $t$. Here we obtained a circuit with $n$ inputs $e_1, e_2, \ldots, e_n$, and its output is the truth value of $t = \sum_{e_i = 1} x_i$, which is a CIRCUIT-SAT problem. Moreover we can convert this circuit to FORMULA-SAT, which is trivial.

Answer 2

The Cook-Levin theorem demonstrates a reduction from SUBSET-SUM to SAT.

If you wanted a reduction from SAT to SUBSET-SUM, then yes, such a reduction exists; SUBSET-SUM is NP-complete, and thus the existence of such a reduction follows from the definition of NP-completeness. You should be able to take any standard proof of NP-completeness for SUBSET-SUM and chain the reductions together to get the desired reduction.