How to reduce 3-SAT to subset sum problem?


The trick to the reduction is to use numbers to encode statements about the 3CNF formula, crafting those numbers in such a way that you can later make an arithmetic proposition about the numbers that is only true if the original 3CNF formula is satisfiable. The reduction below is lifted directly from the lecture notes found at https://people.clarkson.edu/~alexis/PCMI/Notes/lectureB07.pdf .

We reduce 3SAT to SUBSET-SUM. Consider a 3CNF formula with variables $x_1, . . . , x_n$ and clauses $c_1, . . . , c_r$. For each variable $x_i$, we will have two numbers $y_i$ and $z_i$ in the list. For each clause $c_j$, we will also have two numbers $s_j$ and $t_j$. We define all of these numbers by specifying their base 10 representations. The construction is best explained by an example and a picture.

If the formula is $(x_1∨x_2∨\overline{x_3})∧(\overline{x_1}∨x_2∨\overline{x_3})$, then the base 10 representations of the numbers will look like this:

\begin{array}{c|ccc|cc} & x_1 & x_2 & x_3 & c_1 & c_2 \\ \hline y_1 & 1 & 0 & 0 & 1 & 0 \\ z_1 & 1 & 0 & 0 & 0 & 1 \\ y_2 & 0 & 1 & 0 & 1 & 1 \\ z_2 & 0 & 1 & 0 & 0 & 0 \\ y_3 & 0 & 0 & 1 & 0 & 0 \\ z_3 & 0 & 0 & 1 & 1 & 1 \\ \hline s_1 & 0 & 0 & 0 & 1 & 0 \\ t_1 & 0 & 0 & 0 & 1 & 0 \\ s_2 & 0 & 0 & 0 & 0 & 1 \\ t_2 & 0 & 0 & 0 & 0 & 1 \\ \hline k & 1 & 1 & 1 & 3 & 3 \\ \end{array}

The number $y_i$ corresponds to the positive occurrences of $x_i$ in the formula while the number $z_i$ corresponds to its negative occurrences. It should be clear how to generalize this construction to an arbitrary 3CNF formula. And the list of numbers can clearly be constructed in polynomial time. We claim that a subset of these numbers adds to exactly $k$ if and only if the formula is satisfiable. A key point is that the sum of the numbers can be done column by column, independently, because carries will never occur.

The $s$ value is crafted the same way for each clause; put a one in the digit position corresponding to that clause, and zeroes everywhere else. The $t$ value will be the same as the $s$ value for each clause.

The $k$ value is always 1111... followed by 33333.... where the number of ones is the same as the number of distinct variables in the formula and the number of threes is the number of clauses in the formula. Note that the required sum $k$ has a one in each digit position corresponding to the variables. This means that any solution to the subset sum problem can include only encoded statements about either a positive instance of the variable or a negative instance in each clause, not both. Note also that sum $k$ has a three in the digit position corresponding to each clause. The $s$ and $t$ values for each clause will sum to two, but to complete the sum a third one will have to come from one of the $y$ or $z$ values. All three ones could come from the $y$ and $z$ values, but the fact that $s$ and $t$ will only sum to two for any clause guarantees that any empty clause in the 3CNF formula forces the subset sum problem to become unsatisfiable.

  • $\begingroup$ How did you determine to use 3? $\endgroup$ – Keefer Rourke Dec 9 '19 at 21:47
  • $\begingroup$ The s and t rows guarantee that you can make 0, 1 or 2 in any of the c columns independent of the y and z values. But to make 3 you must get part of the sum from the y and z rows and those rows indicate a true literal in some clause represented by the c columns. You must sum to 3 in all those columns, hence you must satisfy all those clauses with at least one of the y or z rows, with the rest of the needed sum coming from the s and t rows. ... $\endgroup$ – Kyle Jones Dec 9 '19 at 23:41
  • $\begingroup$ (cont'd) Less than 3 would not demand a true literal in each clause. More than 3 would demand more than one true literal in each clause, which goes beyond the requirements of 3-SAT. $\endgroup$ – Kyle Jones Dec 9 '19 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.