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 pseudopolynomial dynamicprogramming solution. However, I’m less intrigued by the NP proof and more by the NPhardness proof which I present below.
Subset Sum is NP hard
Proof: We’ll construct a polynomial reduction from 3CNFSAT (3literal per clause Conjunctive Normal Form Satisfiability) problem. Let Ψ be a 3CNF 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+mi} + 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+mi} + 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^{mj}
 h_{j} = 10^{mj}
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:
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}.

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?