I think it's more accurate to say that NP-complete problems have at least some cases that cannot be solved efficiently. That's not to say that the average case

I think it's more accurate to say that NP-complete problems have at least some cases that cannot be solved efficiently. That's not to say that the average case is hard -- in fact, most instances that you're likely to run across in the real world might be quite easy. That's pretty much what the author is arguing here: > Due to the tremendous amount of work that has been done on the Traveling Salesman Problem, the TSP is one such problem. If you have an instance of the TSP of practical interest (i.e. it makes a difference to your life if you solve it or not, and it is really a TSP, not the result of some weird set of set of reductions from some other problem), then I bet you the Concorde program of Bill Cook and others will get you a provably optimal solution in a reasonable amount of time. The difference between problems that are hard in the average case, and those that are only hard in the worst case, is really important in cryptography. The knapsack cryptosystem is a good example of this: https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac...