5 ms·

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 li

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 10y 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 10y 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 10y 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 10y 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 10y 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 10y 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 10y 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?
        jsprogrammer 10y ago
        >I suspect such a reduction would significantly inflate the size of your problem. If Metric TSP and a more general TSP are both NP-complete then there is an algorithm in P to transform a general TSP to a Metric TSP. So, a reduction could inflate the size of the problem, but that inflation will not be significant relative to the most naive approach. Here is a SE algorithm: http://cstheory.stackexchange.com/a/14049 http://cstheory.stackexchange.com/a/14049
- Ono-Sendai 10y ago
  Sorting is done by using information from comparisons to discard something like 50% of the remaining possible permutations at once.

yongjik 10y 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 10y 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 10y 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 10y 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 10y 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 10y 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 10y 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?
        jsprogrammer 10y ago
        >I suspect such a reduction would significantly inflate the size of your problem. If Metric TSP and a more general TSP are both NP-complete then there is an algorithm in P to transform a general TSP to a Metric TSP. So, a reduction could inflate the size of the problem, but that inflation will not be significant relative to the most naive approach. Here is a SE algorithm: http://cstheory.stackexchange.com/a/14049 http://cstheory.stackexchange.com/a/14049
Ono-Sendai 10y ago
Sorting is done by using information from comparisons to discard something like 50% of the remaining possible permutations at once.