Proving NP Completeness of a subset-sum problem - how?

Question

So I'm trying to understand P/NPC problems. The one I'm trying to tackle now is subset sum (we have a collection of integers $S$ and a $k$ param: is there a subset of $S$ that sum of all it's elements is equal to $k$?) problem and the proof that ss is an NPC problem by reduction from 3SAT.

I've found two PDF's that attempt to solve that, but the problem is, I don't have the foggiest idea how to 'explain in in my own words'.

Okay, some links ahead and questions related to them:

Here, on page 4th, there's a logic table for 3SAT clause that apparently proves why ss is NPC, but I don't get it - what exactly are those s and t values, and how does that table proves NPC'ness? And how k is computed in that table? It's simply not clear to me :(

Another link on pages 5 and 6 there are another tables that appear out of nowhere with no explanation that I could understand.

So, if anybody knows what I'm talking about and could help me, please answer :). Or, if it's possible, can anybode give me a simple and straightforward proof why subset sum is NPC?

Answer 1

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. Using the 3SAT -> SUBSET SUM reduction from your lecture notes:

The $y$ values encode statements about which variables have positive literals in which clauses. The $z$ values encode statements about which variables have negative literals in which clauses.

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.