subset-sum and partition

Here are two homely-sounding number puzzles that are secretly NP-complete. SUBSET-SUM: given a multiset of positive integers and a target T, is there a subset that adds up exactly to T? (Can you pick some of these bills to total exactly 100 dollars?) PARTITION: can you split a multiset of numbers into two groups with EQUAL sums? (Can two people share a pile of differently-priced items so each pays the same total?) Both feel like arithmetic, not graph theory, which makes them the go-to hard problems whenever you reduce to something involving numbers or weights.

Both are in NP: the certificate is just the chosen subset, and the verifier adds up the selected numbers and compares to the target — clearly polynomial. For hardness, the key fact is that PARTITION is a special case of SUBSET-SUM: a multiset with total sum S can be partitioned into two equal halves exactly when it has a subset summing to S/2 (the rest then also sums to S/2). So partition <=p subset-sum trivially. The reverse reduction, subset-sum <=p partition, is a neat trick: given numbers a1, ..., an with target T and total S, add two extra numbers, S + T and 2S - T (both positive). The new total is 4S, so an equal partition needs each side to sum to 2S. The two big numbers cannot sit together (they already exceed 2S), so they land on opposite sides; balancing forces the original elements accompanying 2S-T to sum to T (equivalently, those on the S+T side sum to S-T). Hence the new instance has an equal partition iff the original had a subset summing to T. To anchor it all, 3-SAT <=p subset-sum via a digit-gadget reduction (each variable contributes a number with a 1 in its own column and in the columns of clauses it satisfies; the target is chosen so columns add up correctly), proving subset-sum NP-complete; partition inherits it.

These two are the favourite seeds for proving NUMERIC problems hard — bin packing, scheduling on two machines, knapsack feasibility — because their inputs are plain numbers that other arithmetic problems can absorb. But there is a crucial honesty here, the pseudo-polynomial trap. Subset-sum HAS a dynamic-programming algorithm running in O(n * T) time, which looks polynomial. It is not: T is a number written in about log T bits, so its input length is log T, and O(n * T) is exponential in that length — this is 'pseudo-polynomial', fast only when the numbers are small. The NP-completeness lives precisely in instances with LARGE numbers (many bits), where the DP table becomes astronomically wide. So subset-sum is a textbook lesson that 'there's a polynomial-looking algorithm' can be a mirage created by an unfair (effectively unary) view of the input size.