> Nobody compares all N! permutation for sorting, and nobody checks all N! tours when solving a TSP.
Doesn't this depend on what you mean by 'solve'? If you really want the single best solution, you're stuck with checking all N! solutions. If you want a solution which merely works pretty well almost all of the time, then you're right, there are many polynomial time solutions.
I wasn't able to read the Scientific American article that the author ranted against, but if it's discussing TSP from a mathematical standpoint, I wouldn't fault them for discussing the feasibility of checking all N! permutations... that's exactly how it was discussed to me in my introductory computation classes.
Doesn't this depend on what you mean by 'solve'? If you really want the single best solution, you're stuck with checking all N! solutions. If you want a solution which merely works pretty well almost all of the time, then you're right, there are many polynomial time solutions.
I wasn't able to read the Scientific American article that the author ranted against, but if it's discussing TSP from a mathematical standpoint, I wouldn't fault them for discussing the feasibility of checking all N! permutations... that's exactly how it was discussed to me in my introductory computation classes.