# Reduce Subset-Sum to Sat

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

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.