Karp's Classics Challenge 1: Knapsack to Partition
October 20, 2023In 1972, Richard Karp published a paper titled "Reducibility Among Combinatorial Problems," in which he demonstrated that 21 decision problems were NP-complete. What is fascinating is that, until this…