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