Unfortunately, the problems he reduces from are not so hard in practice. Knapsack has what's called an FPTAS, which means you can get as good an approximation a

Unfortunately, the problems he reduces from are not so hard in practice. Knapsack has what's called an FPTAS, which means you can get as good an approximation as you want, and the runtime only scales polynomially with your desired accuracy. And independent set has nice approximation algorithms for bounded degree graphs and other restricted graph classes (though there is no general constant-factor approximation unless P = NP). So it's funny that the author quotes knapsack as the possible true difficulty...