Subset sum and the secret language of numbers
Kent Quanrud · 54:37
Subset sum looks as easy as making change, but this lecture shows why the natural \(O(nT)\) DP is only pseudo-polynomial and then proves the problem is as hard as 3-SAT by packing many SAT constraints into the digits...