5 ms·

The title makes it sounds much worse than it actually is. I mean, this isn't that bad: > But what about going to 100 different cities? A computer would have t

• merraksh 11y ago
  I think this is just one of the pitfalls that the author points out: it is not the sheer number of possibilities that defines the difficulty of a problem. He links to his previous blog post http://mat.tepper.cmu.edu/blog/?p=6995 http://mat.tepper.cmu.edu/blog/?p=6995 with a nice example: sorting. “Sorting a bunch of numbers! Hoo-wee, that’s a hard one. If I had 1000 numbers, I would have to check all orderings of the numbers to find the sorted order. That is 1000999998…21 orders and that is more than the hairs on a Hobbit’s toes.”
  • yongjik 11y ago
    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.) On the other hand, TSP almost certainly does not have any O(N^k) algorithm, for any fixed k. Sure, the difference between (say) N^200 and N! is huge, but an introductory article cannot explain every details. 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!. His posts read more like an advertisement for his research area (optimization) than actual complaint. Well, that's not a bad thing, but I feel the title is a bit clickbait-ish...
    • mayank 11y ago
      > Nobody sorts by comparing all N! permutations and picking the correct one. (Well, I certainly don't.) You can usually make a problem seem harder than it actually (from a complexity point of view) is by phrasing it in terms of directly picking from permutations or combinations. An example: finding the longest common substring for N strings can also be phrased as picking from a quadratic number of of substrings, but has a linear-time algorithm (using suffix trees).
    • merraksh 11y ago
      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).
      • jsprogrammer 11y ago
        I have seen many TSP solvers that enumerate known incorrect solutions. For example, a TSP solution will have no intersecting paths, but many solvers will generate and check solutions with intersecting paths all day long.
        • gamegoblin 11y ago
          Your heuristic is only valid for the Metric TSP problem, not the general TSP problem. That is, graphs do not need to be embedded in some physical space in which "intersecting paths" exist.
          • jsprogrammer 11y ago
            All NP-complete problems should be reducible to the Metric TSP problem. You would only need to transform your more general problem to use this "heuristic".
            • gamegoblin 11y ago
              I suspect such a reduction would significantly inflate the size of your problem. I say this because there exist algorithms such as Christofides algorithm which explicitly work on Metric TSP. If there were such a trivial transformation that preserved the complexity class, why wouldn't Christofides algorithm apply to the general case?
    • Ono-Sendai 11y ago
      Sorting is done by using information from comparisons to discard something like 50% of the remaining possible permutations at once.