But sorting has a known O(N log N) algorithm. Nobody sorts by comparing all N! permutations and picking the correct one. (Well, I certainly don't.)
That is precisely the point of the blog post. Nobody compares all N! permutation for sorting, and nobody checks all N! tours when solving a TSP. The latter is less trivial because algorithms that solve the TSP are far more sophisticated than a sorting algorithm, but they still avoid enumerating a very large subset of solutions. They cannot be claimed to run in polynomial time for any instance, but they are still quite efficient.
Saying that TSP is as hard as N! is technically wrong, but it's much less wrong than saying sorting is as hard as N!.
I disagree, both from a practical standpoint (in both cases there are orders of magnitude between N! and actual CPU time) and a more metaphysical one (neither algorithm explores the full set of solutions).
That is precisely the point of the blog post. Nobody compares all N! permutation for sorting, and nobody checks all N! tours when solving a TSP. The latter is less trivial because algorithms that solve the TSP are far more sophisticated than a sorting algorithm, but they still avoid enumerating a very large subset of solutions. They cannot be claimed to run in polynomial time for any instance, but they are still quite efficient.
Saying that TSP is as hard as N! is technically wrong, but it's much less wrong than saying sorting is as hard as N!.
I disagree, both from a practical standpoint (in both cases there are orders of magnitude between N! and actual CPU time) and a more metaphysical one (neither algorithm explores the full set of solutions).