[thxg]

> The best-known algorithms for NP-complete problems are essentially searching for a solution from all possible answers. The traveling salesman problem on a graph of a few hundred points would take years to run on a supercomputer.

This shortcut in explaining NP-completeness is frustratingly widespread. It is also very wrong. A 49-city TSP was solved (to provable optimality) by hand by 1954 [1]. Concorde [2] can solve TSP instances with more than a hundred thousand cities [3]. In practice, for a graph with a few hundred points, you will most likely find an optimal tour in minutes on an iPhone (yes, there is an app for that [4]).

And it's not just about TSP. SATs [5] and MIPs [6] with hundreds of thousands of variables are solved every day to provable optimality. How? Well, sure, the best-known algorithms for NP-complete problems are of course exponential in the worst-case. But they are definitely not "essentially searching for a solution from all possible answers", that would indeed be prohibitively costly. We have algorithms that perform much better on practical instances (dynamic programming, backtracking, branch-and-bound, etc.).

[1] https://www.math.uwaterloo.ca/tsp/uk/history.html

[2] https://www.math.uwaterloo.ca/tsp/concorde/index.html

[3] https://www.math.uwaterloo.ca/tsp/star/about.html

[4] https://apps.apple.com/us/app/concorde-tsp/id498366515

[5] http://www.satcompetition.org/

[6] http://plato.asu.edu/ftp/milp.html