Reduce subset sum to 3SAT

Question

How to do it? I'm not asking the solution for the proof of why subset sum is NPC, but rather the opposite reduction

Answer 1

The trick to reducing any NP problem to SAT is 1) writing a subroutine that checks the polynomially-sized certificate, 2) converting that routine to a circuit, and 3) flattening the circuit to CNF using the usual methods.

For example, to convert integer factorization to SAT, you would write a routine that multiplies two $n$-bit multipliers producing a 2$n$-bit result. Convert the routine to a circuit, then convert the circuit to CNF. Then add simple declarative CNF clauses that force the $2n$ output variables of the circuit to match the bits of the integer that you want to factor. The resulting CNF instance will be satisfiable only if a bit pattern for the two $n$-bit numbers exists that when multiplied together produces the 2$n$-bit number you want factored. (If you want trivial solutions excluded then you also need to add two extra CNF clauses that demand the most significant $n$-1 bits of each multiplier are not all zero.)

Subset sum is a bit more intricate. You need to write $n$ routines, each of which returns a particular one of the $n$ integers of the problem set or zero depending on the setting of a parameter bit. These routines feed input into another routine you wrote that sums all $n$ of its inputs and outputs the result. Convert all this into a circuit whose inputs are the parameter bits and whose outputs are the result of the addition routine. Convert the circuit to CNF. Add declarative CNF clauses that force the output variables of the adder routine to match the bits of $k$, the number a solution must sum to. The resulting CNF instance will be satisfiable only if there exists a bit pattern of the parameter bits selecting a subset of the problem set that sums up to $k$.

Answer 2

Usually, there are no intuitive or enlightening reductions between problems in different problem domains.

The proof that 3SAT is NP-complete is essentially by writing a formula that says "This NP Turing machine accepts this input." For other problems about logical formulas, you can often translate the formula into a 3SAT instance. Sometimes, you can express problems in other domains as 3CNF formulas: for example, you can do 3-colourability by having variables for each combination of "vertex $v$ has colour $q$" and write a formula that says that each vertex has exactly one colour and adjacent vertices have different colours.

However, usually, when you're faced with a problem from a completely different domain, you can't do much better than say that subset sum is in NP so it's decided by a Turing machine that I can express as a 3SAT instance. Perhaps you can come up with a less generic reduction, but it probably wouldn't teach you anything.