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
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.