I never expected to dedicate a casual blog entry to a hardness proof, especially one fairly academic as this. However, the nature of it evokes certain elegance beyond what I typically encounter in the domain. Authentic theoreticians may not sympathize with this excitement. Yet I find enough aesthetic substance in the matter to indulge in the exercise that follows.

**Introduction**

*Subset Sum*: given a set *A* of integers, and an integer *k*, does some subset *S* of *A* sum to *k*?

Subset Sum is a NP Complete problem, possessing a pseudo-polynomial dynamic-programming solution. However, I’m less intrigued by the NP proof and more by the NP-hardness proof which I present below.

**Subset Sum is NP hard**

*Proof*:
We’ll construct a polynomial reduction from 3-CNFSAT (3-literal per clause Conjunctive Normal Form Satisfiability) problem. Let Ψ be a 3-CNF formula with *n* variables and *m* clauses. Let’s build set *A* as follows:

For each variable x_{i}, 1 ≤ i ≤ n, append the following two integers to *A*:

- y
_{i}= 10^{n+m-i}+ c_{1i}c_{2i}…c_{mi}, where digit c_{ji}is 1 if literal x_{i}appears in clause j, and 0 otherwise. - z
_{i}= 10^{n+m-i}+ d_{1i}d_{2i}…d_{mi}, where digit d_{ji}is 1 if the negative literal ¬x_{i}appears in clause j, and 0 otherwise.

Then for each clause c_{j}, add two rows

- g
_{j}= 10^{m-j} - h
_{j}= 10^{m-j}

Finally, let k = int(1^{n}3^{m}) (exponents in string arithmetic).
This concludes our reduction.

For example, the formula

(x_{1} ∨ x*2 ∨ x*3) ∧ (¬x_{2} ∨ x_{3} ∨ x_{4}) ∧ (x_{1} ∨ ¬x_{2} ∨ ¬x_{3})

yields the following set *A* and *k*:

A | x_{1}x_{2}x_{3}x_{4},c_{1}c_{2}c_{3} |
---|---|

y_{1} |
1 0 0 0, 1 0 1 |

z_{1} |
1 0 0 0, 0 0 0 |

y_{2} |
1 0 0, 1 0 0 |

z_{2} |
1 0 0, 0 1 1 |

y_{3} |
1 0, 1 1 0 |

z_{3} |
1 0, 0 0 1 |

y_{4} |
1, 0 1 0 |

z_{4} |
1, 0 0 0 |

g_{1} |
1 0 0 |

h_{1} |
1 0 0 |

g_{2} |
1 0 |

h_{2} |
1 0 |

g_{3} |
1 |

h_{3} |
1 |

k | 1 1 1 1 3 3 3 |

Note, k = 1111333 for the current example, given 4 variables and 3 clauses.

*Reduction correctness*

- The reduction trivially constructs
*A*in polynomial time. Assignment

*t*satisfies Ψ ==> exists subset*S*of*A*that sums to k:Construct

*S*as follows:- Add y
_{i}to*S*if t(x_{i}) is true, and z_{i}if t(x_{i}) is false. - For each clause c
_{j}, add g_{j}to*S*if less than 3 literals are satisfied in c_{j}, and additionally add h_{j}if less than 2 literals are satisfied.

The elements of

*S*sum to*k*: since we add only y_{i}or z_{i}to*S*, every significant (variable) digit will contain a 1, and every insignificant (clause) digit will contain a 3, the sum of the number of literals satisfied in c_{j}plus the number of literals not satisfied (maximum two), compensated by g_{j}and h_{j}.- Add y
Assignment

*t*doesn’t satisfy Ψ ==> no subset*S*of*A*exits that sums to k:Since we cannot satisfy Ψ, exists some clause c

_{j}that cannot be satisfied irrespective of the truth assignment. Given an arbitrary assignment*t*, clause c_{j}doesn’t contain a single literal that would satisfy it, and the y_{i}or z_{i}added to*S*would contain a 0 in the respective decimal point. Consequently,*S*can only sum to 2 in that decimal point from the compensating g_{j}and h_{j}.

*End of proof*

**Conclusion**

This proof draws inspiration from CLRS, but as I don’t presently have access to the full text, I can’t ascertain the original source. Does my somewhat terse coverage make sense? Do you find this sort of proof admirable, or entirely unremarkable?

**Questions, comments**? Connect.