12 ms·

“American Scientist” Understands Nothing about the Traveling Salesman Problem

128 points by merraksh 10y ago

pavel_lishin 10y ago
> I don’t know if this means I should not trust American Scientist in areas that are not my specialty. On something I know a bit about, the magazine has failed miserably. I forget the term for this - when we see media cover something we know about badly, but continue to assume that they cover other topics that we're relatively ignorant about fairly and correctly.
- spacemanmatt 10y ago
  Odd, when I see something that offends my area of expertise, it causes me significant skepticism on everything else from that source. I need it to be right about things I know are right, or I can't trust it on things I truly know less about.
- mikeash 10y ago
  It's called the Gell-Mann Amnesia Effect.
  - metaphorm 10y ago
    be careful with that. as far as I can tell from my own investigations into it, Murray Gell-Mann did not coin this term or have much of anything to do with it. Murray Gell-Mann himself was a quantum physicist and I don't think he spent a lot of time worrying about the news media. I believe the "Gell-Mann Amnesia Effect" is something created by the fiction author Michael Crichton as a plot device. It may be an interesting idea but as far as I know it is not a real researched effect in media studies or psychology.
    - mikeash 10y ago
      I'm not sure what there is to be careful of here. A brief search will reveal that it was named after Gell-Mann in an attempt to make it sound better, and I don't see any particular implication from it that it's a scientifically supported phenomenon.
      - chris_wot 10y ago
        You only need to be careful because some smart-alek will point out it is an example of Stigler's law of eponymy.
      - metaphorm 10y ago
        I'm saying you should be careful because it is easy to give a false impression that you are discussing a scientifically supported phenomenon where really it is basically the musings of a fiction writer. the name "Gell-Mann Amnesia" was, in fact, chosen by Crichton self-consciously so that this false impression would be more likely in discussions such as this one. Lack of context and a fancy sounding name serve to obfuscate the truth here.
        mikeash 10y ago
        Is it really? People throw around fancy-sounding names like Betteridge's Law of Headlines and Sturgeon's Law without any qualifiers and nobody seems to mistake those for scientific principles. I'm not sure it's worth defending against people taking a fancy-sounding name and taking that as an indication that it's scientific principle without even bothering to take five seconds to look it up.
        metaphorm 10y ago
        Betteridge's Law is named after Ian Betteridge, a technology journalist, who wrote directly on the subject. Sturgeon's Law is named after Ted Sturgeon, a fiction writer, who actually basically coined the phrase originally (I think he did anyway). Michael Crichton, on the other hand, did not call his idea "Crichton's Law of Media Analysis". He deliberately gave it an obfuscatory name and attempted to associate it with a well regarded physicist to give the impression that the law was scientific in some way. It was a deliberate misdirection, done for effect. Because of the intrinsically duplicitous nature of the name "Gell-Mann Amnesia" I think its inappropriate to continue referring to the effect under that name. Call it Crichton's Law or whatever. Lets not repeat the original misdirection though. It is fundamentally dishonest and does a disservice to the legacy of Murray Gell-Mann.
    - 33W 10y ago
      While mikeash covered that badly, I'll continue to assume that they cover other topics that we're relatively ignorant about fairly and correctly.
    - kragen 10y ago
      Gell-Mann still is a quantum physicist. Don't scare me like that.
      - sago 10y ago
        I know!, I was all "oh jeez, not Murray too, how did I not hear about that!". Okay, panic over.
    - 1812Overture 10y ago
      A great example of Stigler's Law of Eponymy: https://en.wikipedia.org/wiki/Stigler%27s_law_of_eponymy https://en.wikipedia.org/wiki/Stigler%27s_law_of_eponymy
- rrauenza 10y ago
  I learned this early as a child. I stood next to my dad as he was interviewed by a journalist for a community event where he worked. When I later read the actual article, I was somewhat astounded by the inaccuracy. And I was a child!
  - lotharbot 10y ago
    I learned this watching TV coverage of a particular protest/rally I had been to. There were no shots of the diverse crowd of thousands, only a single close-up of an old man who was dressed oddly. The much smaller counter-protest of ~10 people got more airtime, but instead of showing them yelling and cussing at the children in our group, a well-dressed female lawyer from their side was interviewed, with a few others packed around her and a tight camera angle to make it look like she was in the middle of a huge crowd. Like, it wasn't just mildly inaccurate coverage as a result of the reporters not having good enough understanding. It was intentionally slanted coverage. And it made me think, if they can make something that straightforward look so different from reality, I have a hard time trusting their coverage in general. (See also: Babylon 5 season 4 episode 8 "The Illusion of Truth")
  - rlonstein 10y ago
    https://en.wikipedia.org/wiki/Erwin_Knoll https://en.wikipedia.org/wiki/Erwin_Knoll First hand experience with Knoll's Law of Media Accuracy: Everything you read in the newspapers is absolutely true except for the rare story of which you happen to have firsthand knowledge I heard it first phrased (and probably before the above) that the accuracy of a newspaper article is inversely proportional to how close you are to the subject.
  - jandrese 10y ago
    One of the things I noticed in college was that the journalism major seemed to attract a class of people who are not good at comprehending complex systems. If you don't understand something, it's almost impossible to communicate the concept of it to another person. My dad was a chemical engineer and whenever News 7 had a story about the chemical plant my dad would mutter about how they got the details (and pronunciations!) all wrong.
- dmd 10y ago
  This is why I can't read any of Bill Bryson's books. As far as I can tell, they're researched by copying "facts" off "DID YOU KNOW???" children's diner placemats, for all the things I actually know about, so I have to assume everything else is like that too.
- lukev 10y ago
  This is even more true of the comment section of HN than it is in the media. For several domains I know something about, the comments here are painfully misguided and just bad, with the possible exception of some programming topics.
  - logicallee 10y ago
    > For several domains I know something about, the [HN] comments are painfully misguided and just bad But in the case of HN, if you leave them that way in a way it's your fault :-P Meaning, that you could write a paragraph or two setting the rest of us straight. The exception is subjects that are extremely politically sensitive and controversial, in which your paragraph or two could be downvoted to oblivion and start a uselessly derailed thread, no matter how incredibly polite you are. If HN has 'groupthink' opinion that is completely wrong on kernel scheduling, you can set it right, politely and by sticking to the facts. If HN has 'groupthink' opinion that is completely wrong on a political or other controversial issue, I would politely abstain.
    - chongli 10y ago
      If HN has 'groupthink' opinion that is completely wrong on a political or other controversial issue, I would politely abstain. No way! I love commenting on political and controversial issues. Never let a fear of downvotes act as a chilling effect on your speech. If you believe you have something truly valuable to add then get it out there! I often find myself surprised that I'm upvoted for swimming against the current. It may turn out that there were multiple people who had the same idea as me but they were staying out of it until I commented.
      - lotharbot 10y ago
        or, in many cases, people who agree but couldn't express the same idea as well as you, or even people who disagree but learned something. Upvotes aren't only a sign of likemindedness.
        10y ago
- make3 10y ago
  To me, this is basic credibility, not anything special. people will trust you less if you mess up the things they know something about, rightly so.
- mikestew 10y ago
  Yeah, I don't know what the term is, either. But I learned the lesson early on. Even amongst those in the know, reserve accepting the words as truth as even knowledge people don't know when to quit when they reach the perimeter of their ignorance. Take a most recent example that has nothing to do the topic at hand: VW Vanagon camper vans. We took our '81 Westy to a campout that was a bunch of VW Westfalia camper vans (with the cute pop-top tents on the roof, for the uninitiated). Think these folks can bore you with the intimate details of Westies you never knew you didn't care about? Ohhhhh, yeah. These folks know their Westies, and they'll make you wish you never asked. A couple of ladies are admiring ours (as well they should, as it's in excellent shape). They were debating whether the rear air intakes should be metal or plastic. They were absolutely sure that an early Vanagon such as ours should have metal. They were mostly right. Except for the part where VW put out a diesel version in the middle of the '81 model year, at which time VW switched to plastic air intakes for all models. My point? Oh, I've got one, bear with me. The point is that even when knowledgable people get most of the details right, don't assume that every single detail is correct. In the example of the article, they got most of the way there and then...didn't know when to quit. It seems to me that they started the article with a decent, but not great, grasp of the topic. When they hit the parts that they were a little fuzzy on, they trudged on regardless, got it wrong, and now some question everything they've published. The authors were knowledgable, but not experts, but that didn't stop them from writing like they are experts. Or something something Dunning-Kruger, I'm not sure.
carlob 10y ago
It's weird, I remember reading a very informative article about SAT from American Scientist when I was an undergrad: http://sjcomp.com/files/compsci9703.html http://sjcomp.com/files/compsci9703.html I will have to reread it to see if it still makes sense.
spdegabrielle 10y ago
The Brian Hayes articles were always awesome - sadly he has gone.
- jamessb 10y ago
  I don't think he has gone: both his blog [0] and the American Scientist site [1] refer to him as a senior writer in the present tense, and he had an article about deep dreaming in the Nov-Dec 2015 issue [2]. His blog is interesting, and has posts more frequent than his magaine articles. [0]: http://bit-player.org/about-the-author http://bit-player.org/about-the-author [1]: https://www.americanscientist.org/authors/detail/brian-hayes https://www.americanscientist.org/authors/detail/brian-hayes [2]: https://www.americanscientist.org/issues/pub/2015/6/computer-vision-and-computer-hallucinations https://www.americanscientist.org/issues/pub/2015/6/computer...
pierrebai 10y ago
Yes! One politic is found to be corrupt, all politicians must be corrupt! One businessman implemented a fraud, down with captalism! One autistic child took several vaccine before being diagnosed. VAccine are the culprit! I see, read, and hear these kind of argument all the times and they sadden me. I'm sure Snake-oil salesman, con artist and populist politicans salivates when reading how easily people dismiss things so easily. Is the American Scientist article entirely wrong? No. Is even just that sideboard entirely off-track? No. It's probably a case of vulgarization gone too far. But hey, baby, water, bath, plumbing, out the window you go.
- _dark_matter_ 10y ago
  Hey, great job, you just took it to the other side of the spectrum! But seriously, it's a question of evidence, in every case you mentioned. The null hypothesis being "nothing is wrong", which you seem to be pointing at. There are definitely cases where the null hypothesis is NOT true, and needs to be rejected. To muse about whether the evidence is enough is surely an appropriate practice, which seems to be what the author is doing.
yongjik 10y ago
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 to check 100x99x98x….x2x1 possible routes. Yes, the sentence should have included "In case of a brute-force search", but still it conveys the basic idea of TSP and why it gets exponentially harder as N increases.
- merraksh 10y 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 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).
louprado 10y ago
As an aside, an algorithm based on ant pheromones is a clever way to solve the traveling salesman problem. http://people.idsia.ch/~luca/acs-bio97.pdf http://people.idsia.ch/~luca/acs-bio97.pdf
- merraksh 10y ago
  But ant colony algorithms are heuristics. The Concorde software by Cook and co., that is mentioned in the blog post, obtains an optimal solution.
  - chris_wot 10y ago
    Yes, but the ant colony algorithm is interesting... and kind of neat!
simulate 10y ago
Bill Cook, mentioned in this post, has written an excellent and entertaining book on the TSP that is accessible to non-experts: http://www.amazon.com/Pursuit-Traveling-Salesman-Mathematics-Computation/dp/0691152705 http://www.amazon.com/Pursuit-Traveling-Salesman-Mathematics... If you're not interested in reading an entire book on the topic, Cook's webpage provides a summary and includes several examples: http://www.math.uwaterloo.ca/tsp/ http://www.math.uwaterloo.ca/tsp/ Finally, here's a simple version of the TSP showing route optimization in San Francisco using local businesses: https://forio.com/app/showcase/route-optimizer/ https://forio.com/app/showcase/route-optimizer/
- cvwright 10y ago
  Maybe American Scientist should have Bill Cook write a follow-up article for them to explain the current state of the art.
leecarraher 10y ago
If you are offended by a pop science magazine's over simplification of a topic that resides in a field you have some specialty understanding of, you clearly haven't been reading pop-sci magazines for very long. You have all the right in the world to be angry when this happens in a journal article, but you are reading American Scientist, not SODA.
- bbarn 10y ago
  Yep. Let's not forget the massive benefit of this - introducing new minds to hard concepts. It doesn't need to be feature perfect and up to date with the latest ideas, just enough to make it interesting to the readers.
- x1798DE 10y ago
  I think that most people believe that popular science press covers science topics in a way that is simplified but mostly accurate (like the statement "there are 86,400 seconds in a day.", which is true enough, neglecting edge cases). The problem is that most popular science, in my experience, fundamentally misrepresents the issues at hand and the stuff that "should be" correct. It's misleading "anti knowledge" in many cases, not just a blurry outline of the topic at hand.
aerovistae 10y ago
I'm confused by this post. I was under the impression NP-complete problems could not be solved efficiently, but the author is saying that TSP, the most well known NP-complete problem, can be solved practically. I read what he wrote but did not understand what he was saying. Why is TSP famously hard if it's actually tractable in practice?
- cvwright 10y ago
  I think it's more accurate to say that NP-complete problems have at least some cases that cannot be solved efficiently. That's not to say that the average case is hard -- in fact, most instances that you're likely to run across in the real world might be quite easy. That's pretty much what the author is arguing here: > Due to the tremendous amount of work that has been done on the Traveling Salesman Problem, the TSP is one such problem. If you have an instance of the TSP of practical interest (i.e. it makes a difference to your life if you solve it or not, and it is really a TSP, not the result of some weird set of set of reductions from some other problem), then I bet you the Concorde program of Bill Cook and others will get you a provably optimal solution in a reasonable amount of time. The difference between problems that are hard in the average case, and those that are only hard in the worst case, is really important in cryptography. The knapsack cryptosystem is a good example of this: https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac...
  - te_platt 10y ago
    Exactly. A good example would be a set of co-linear points. Even for N=1,000,000 if all the points are at (n,0) on the plane then it's pretty trivial to find the solution.
- geofft 10y ago
  I think it's famous because it's one of the most easily understandable NP-complete problems: it has a nice, intuitive "word problem" description. 3SAT has no such intuitive description. Even for those of us who understand boolean formulas, there's no particular intuition about how hard 3SAT (and 2SAT) should be. It's a fairly abstract mathematical construct. NP-complete problems admit no polynomial-time solution for every possible answer, and even if they run in more-than-polynomial time, there's no constraint on what those constants look like. Suppose the best algorithm takes 2^n / 2^100000 seconds. That's definitely more than polynomial, but also pretty fast for real-world problem sizes. It turns out that even SAT solvers are also pretty good in practice on real-world-sized problems, to the point where Fedora's and SUSE's dependency solvers (in dnf and zypper, respectively) convert your package dependencies to an instance of SAT and throw it at a generic SAT solver, because that's better-optimized.
jtolmar 10y ago
That Hilbert Curve solution is really handy to know about. If you were writing a game where the player competes with an AI at traveling salesman (Pacman without the ghosts race), a fast 75% optimal algorithm sounds perfect. I think you can do the Hilbert Curve in n log n time by loading all the cities into a quad tree and traversing it in a Hilberty order. Is that the fastest way?
plank 10y ago
I remember the same feeling, a long time ago. I would read the Dutch 'NRC' science page, and be annoyed that they really did not understand the Schrödinger cat problem. Of course, since then I strayed away from my physics career (entering IT with a PhD in physics), and now I can read those same science pages and think, wow they really know their stuff....
skywhopper 10y ago
"I will get my favorite spaghetti meal served on my birthday." In an otherwise run-of-the-mill rant, this struck me as a truly weird, passive, and ungrammatical (to my ear) assertion. The lack of any agent makes me wonder if he's insisted on his parents and then various friends or significant others over the years to serve him this meal. Or does he hire someone to perform this task for him? The lack of the mention of "cooking" and the phrasing "spaghetti meal" make me envision dumping a cold can of Chef Boy-Ar-Dee spaghetti out in a bowl. Just an odd, unrelatable insistence. Weird.
- spinlock 10y ago
  I smell a startup. Uber for Spagettios.
tater_sent_me 10y ago
It's easy to beat up pop-science. Exhaustively searching for the optimal solution for TSP does take a prohibitive amount of time. Understanding how, why, and coming up with schemes that do allow you to find an optimal solution is what computer scientists have done.
perseusprime11 10y ago
Do they have to know about the Traveling Salesman Problem?
jessaustin 10y ago
This magazine (and its similarly-named rival) sometimes calls to mind Nelson Muntz's comment: "I can think of at least two things wrong with that title."
waldrews 10y ago
Cixin Liu's The Dark Forest has the alien enemy ship solve the traveling salesman problem for a moderate n in real time as a way of demonstrating the aliens' superior level of science. That must upset the original poster almost as much...
SeanDav 10y ago
How does one know one has an optimal solution for the travelling salesman problem? Any experts out there that can explain this, or point to some accessible literature on this?

128 points by merraksh 10y ago

> I don’t know if this means I should not trust American Scientist in areas that are not my specialty. On something I know a bit about, the magazine has failed miserably. I forget the term for this - when we see media cover something we know about badly, but continue to assume that they cover other topics that we're relatively ignorant about fairly and correctly.

spacemanmatt 10y ago
Odd, when I see something that offends my area of expertise, it causes me significant skepticism on everything else from that source. I need it to be right about things I know are right, or I can't trust it on things I truly know less about.
mikeash 10y ago
It's called the Gell-Mann Amnesia Effect.
- metaphorm 10y ago
  be careful with that. as far as I can tell from my own investigations into it, Murray Gell-Mann did not coin this term or have much of anything to do with it. Murray Gell-Mann himself was a quantum physicist and I don't think he spent a lot of time worrying about the news media. I believe the "Gell-Mann Amnesia Effect" is something created by the fiction author Michael Crichton as a plot device. It may be an interesting idea but as far as I know it is not a real researched effect in media studies or psychology.
  - mikeash 10y ago
    I'm not sure what there is to be careful of here. A brief search will reveal that it was named after Gell-Mann in an attempt to make it sound better, and I don't see any particular implication from it that it's a scientifically supported phenomenon.
    - chris_wot 10y ago
      You only need to be careful because some smart-alek will point out it is an example of Stigler's law of eponymy.
    - metaphorm 10y ago
      I'm saying you should be careful because it is easy to give a false impression that you are discussing a scientifically supported phenomenon where really it is basically the musings of a fiction writer. the name "Gell-Mann Amnesia" was, in fact, chosen by Crichton self-consciously so that this false impression would be more likely in discussions such as this one. Lack of context and a fancy sounding name serve to obfuscate the truth here.
      - mikeash 10y ago
        Is it really? People throw around fancy-sounding names like Betteridge's Law of Headlines and Sturgeon's Law without any qualifiers and nobody seems to mistake those for scientific principles. I'm not sure it's worth defending against people taking a fancy-sounding name and taking that as an indication that it's scientific principle without even bothering to take five seconds to look it up.
        metaphorm 10y ago
        Betteridge's Law is named after Ian Betteridge, a technology journalist, who wrote directly on the subject. Sturgeon's Law is named after Ted Sturgeon, a fiction writer, who actually basically coined the phrase originally (I think he did anyway). Michael Crichton, on the other hand, did not call his idea "Crichton's Law of Media Analysis". He deliberately gave it an obfuscatory name and attempted to associate it with a well regarded physicist to give the impression that the law was scientific in some way. It was a deliberate misdirection, done for effect. Because of the intrinsically duplicitous nature of the name "Gell-Mann Amnesia" I think its inappropriate to continue referring to the effect under that name. Call it Crichton's Law or whatever. Lets not repeat the original misdirection though. It is fundamentally dishonest and does a disservice to the legacy of Murray Gell-Mann.
  - 33W 10y ago
    While mikeash covered that badly, I'll continue to assume that they cover other topics that we're relatively ignorant about fairly and correctly.
  - kragen 10y ago
    Gell-Mann still is a quantum physicist. Don't scare me like that.
    - sago 10y ago
      I know!, I was all "oh jeez, not Murray too, how did I not hear about that!". Okay, panic over.
  - 1812Overture 10y ago
    A great example of Stigler's Law of Eponymy: https://en.wikipedia.org/wiki/Stigler%27s_law_of_eponymy https://en.wikipedia.org/wiki/Stigler%27s_law_of_eponymy
rrauenza 10y ago
I learned this early as a child. I stood next to my dad as he was interviewed by a journalist for a community event where he worked. When I later read the actual article, I was somewhat astounded by the inaccuracy. And I was a child!
- lotharbot 10y ago
  I learned this watching TV coverage of a particular protest/rally I had been to. There were no shots of the diverse crowd of thousands, only a single close-up of an old man who was dressed oddly. The much smaller counter-protest of ~10 people got more airtime, but instead of showing them yelling and cussing at the children in our group, a well-dressed female lawyer from their side was interviewed, with a few others packed around her and a tight camera angle to make it look like she was in the middle of a huge crowd. Like, it wasn't just mildly inaccurate coverage as a result of the reporters not having good enough understanding. It was intentionally slanted coverage. And it made me think, if they can make something that straightforward look so different from reality, I have a hard time trusting their coverage in general. (See also: Babylon 5 season 4 episode 8 "The Illusion of Truth")
- rlonstein 10y ago
  https://en.wikipedia.org/wiki/Erwin_Knoll https://en.wikipedia.org/wiki/Erwin_Knoll First hand experience with Knoll's Law of Media Accuracy: Everything you read in the newspapers is absolutely true except for the rare story of which you happen to have firsthand knowledge I heard it first phrased (and probably before the above) that the accuracy of a newspaper article is inversely proportional to how close you are to the subject.
- jandrese 10y ago
  One of the things I noticed in college was that the journalism major seemed to attract a class of people who are not good at comprehending complex systems. If you don't understand something, it's almost impossible to communicate the concept of it to another person. My dad was a chemical engineer and whenever News 7 had a story about the chemical plant my dad would mutter about how they got the details (and pronunciations!) all wrong.
dmd 10y ago
This is why I can't read any of Bill Bryson's books. As far as I can tell, they're researched by copying "facts" off "DID YOU KNOW???" children's diner placemats, for all the things I actually know about, so I have to assume everything else is like that too.
lukev 10y ago
This is even more true of the comment section of HN than it is in the media. For several domains I know something about, the comments here are painfully misguided and just bad, with the possible exception of some programming topics.
- logicallee 10y ago
  > For several domains I know something about, the [HN] comments are painfully misguided and just bad But in the case of HN, if you leave them that way in a way it's your fault :-P Meaning, that you could write a paragraph or two setting the rest of us straight. The exception is subjects that are extremely politically sensitive and controversial, in which your paragraph or two could be downvoted to oblivion and start a uselessly derailed thread, no matter how incredibly polite you are. If HN has 'groupthink' opinion that is completely wrong on kernel scheduling, you can set it right, politely and by sticking to the facts. If HN has 'groupthink' opinion that is completely wrong on a political or other controversial issue, I would politely abstain.
  - chongli 10y ago
    If HN has 'groupthink' opinion that is completely wrong on a political or other controversial issue, I would politely abstain. No way! I love commenting on political and controversial issues. Never let a fear of downvotes act as a chilling effect on your speech. If you believe you have something truly valuable to add then get it out there! I often find myself surprised that I'm upvoted for swimming against the current. It may turn out that there were multiple people who had the same idea as me but they were staying out of it until I commented.
    - lotharbot 10y ago
      or, in many cases, people who agree but couldn't express the same idea as well as you, or even people who disagree but learned something. Upvotes aren't only a sign of likemindedness.
      - 10y ago
make3 10y ago
To me, this is basic credibility, not anything special. people will trust you less if you mess up the things they know something about, rightly so.
mikestew 10y ago
Yeah, I don't know what the term is, either. But I learned the lesson early on. Even amongst those in the know, reserve accepting the words as truth as even knowledge people don't know when to quit when they reach the perimeter of their ignorance. Take a most recent example that has nothing to do the topic at hand: VW Vanagon camper vans. We took our '81 Westy to a campout that was a bunch of VW Westfalia camper vans (with the cute pop-top tents on the roof, for the uninitiated). Think these folks can bore you with the intimate details of Westies you never knew you didn't care about? Ohhhhh, yeah. These folks know their Westies, and they'll make you wish you never asked. A couple of ladies are admiring ours (as well they should, as it's in excellent shape). They were debating whether the rear air intakes should be metal or plastic. They were absolutely sure that an early Vanagon such as ours should have metal. They were mostly right. Except for the part where VW put out a diesel version in the middle of the '81 model year, at which time VW switched to plastic air intakes for all models. My point? Oh, I've got one, bear with me. The point is that even when knowledgable people get most of the details right, don't assume that every single detail is correct. In the example of the article, they got most of the way there and then...didn't know when to quit. It seems to me that they started the article with a decent, but not great, grasp of the topic. When they hit the parts that they were a little fuzzy on, they trudged on regardless, got it wrong, and now some question everything they've published. The authors were knowledgable, but not experts, but that didn't stop them from writing like they are experts. Or something something Dunning-Kruger, I'm not sure.

carlob 10y ago

It's weird, I remember reading a very informative article about SAT from American Scientist when I was an undergrad: http://sjcomp.com/files/compsci9703.html http://sjcomp.com/files/compsci9703.html I will have to reread it to see if it still makes sense.

spdegabrielle 10y ago

The Brian Hayes articles were always awesome - sadly he has gone.

jamessb 10y ago
I don't think he has gone: both his blog [0] and the American Scientist site [1] refer to him as a senior writer in the present tense, and he had an article about deep dreaming in the Nov-Dec 2015 issue [2]. His blog is interesting, and has posts more frequent than his magaine articles. [0]: http://bit-player.org/about-the-author http://bit-player.org/about-the-author [1]: https://www.americanscientist.org/authors/detail/brian-hayes https://www.americanscientist.org/authors/detail/brian-hayes [2]: https://www.americanscientist.org/issues/pub/2015/6/computer-vision-and-computer-hallucinations https://www.americanscientist.org/issues/pub/2015/6/computer...

pierrebai 10y ago

Yes! One politic is found to be corrupt, all politicians must be corrupt! One businessman implemented a fraud, down with captalism! One autistic child took several vaccine before being diagnosed. VAccine are the culprit! I see, read, and hear these kind of argument all the times and they sadden me. I'm sure Snake-oil salesman, con artist and populist politicans salivates when reading how easily people dismiss things so easily. Is the American Scientist article entirely wrong? No. Is even just that sideboard entirely off-track? No. It's probably a case of vulgarization gone too far. But hey, baby, water, bath, plumbing, out the window you go.

_dark_matter_ 10y ago
Hey, great job, you just took it to the other side of the spectrum! But seriously, it's a question of evidence, in every case you mentioned. The null hypothesis being "nothing is wrong", which you seem to be pointing at. There are definitely cases where the null hypothesis is NOT true, and needs to be rejected. To muse about whether the evidence is enough is surely an appropriate practice, which seems to be what the author is doing.

yongjik 10y ago

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 to check 100x99x98x….x2x1 possible routes. Yes, the sentence should have included "In case of a brute-force search", but still it conveys the basic idea of TSP and why it gets exponentially harder as N increases.

merraksh 10y 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 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).

louprado 10y ago

As an aside, an algorithm based on ant pheromones is a clever way to solve the traveling salesman problem. http://people.idsia.ch/~luca/acs-bio97.pdf http://people.idsia.ch/~luca/acs-bio97.pdf

merraksh 10y ago
But ant colony algorithms are heuristics. The Concorde software by Cook and co., that is mentioned in the blog post, obtains an optimal solution.
- chris_wot 10y ago
  Yes, but the ant colony algorithm is interesting... and kind of neat!

simulate 10y ago

Bill Cook, mentioned in this post, has written an excellent and entertaining book on the TSP that is accessible to non-experts: http://www.amazon.com/Pursuit-Traveling-Salesman-Mathematics-Computation/dp/0691152705 http://www.amazon.com/Pursuit-Traveling-Salesman-Mathematics... If you're not interested in reading an entire book on the topic, Cook's webpage provides a summary and includes several examples: http://www.math.uwaterloo.ca/tsp/ http://www.math.uwaterloo.ca/tsp/ Finally, here's a simple version of the TSP showing route optimization in San Francisco using local businesses: https://forio.com/app/showcase/route-optimizer/ https://forio.com/app/showcase/route-optimizer/

cvwright 10y ago
Maybe American Scientist should have Bill Cook write a follow-up article for them to explain the current state of the art.

leecarraher 10y ago

If you are offended by a pop science magazine's over simplification of a topic that resides in a field you have some specialty understanding of, you clearly haven't been reading pop-sci magazines for very long. You have all the right in the world to be angry when this happens in a journal article, but you are reading American Scientist, not SODA.

bbarn 10y ago
Yep. Let's not forget the massive benefit of this - introducing new minds to hard concepts. It doesn't need to be feature perfect and up to date with the latest ideas, just enough to make it interesting to the readers.
x1798DE 10y ago
I think that most people believe that popular science press covers science topics in a way that is simplified but mostly accurate (like the statement "there are 86,400 seconds in a day.", which is true enough, neglecting edge cases). The problem is that most popular science, in my experience, fundamentally misrepresents the issues at hand and the stuff that "should be" correct. It's misleading "anti knowledge" in many cases, not just a blurry outline of the topic at hand.

aerovistae 10y ago

I'm confused by this post. I was under the impression NP-complete problems could not be solved efficiently, but the author is saying that TSP, the most well known NP-complete problem, can be solved practically. I read what he wrote but did not understand what he was saying. Why is TSP famously hard if it's actually tractable in practice?

cvwright 10y ago
I think it's more accurate to say that NP-complete problems have at least some cases that cannot be solved efficiently. That's not to say that the average case is hard -- in fact, most instances that you're likely to run across in the real world might be quite easy. That's pretty much what the author is arguing here: > Due to the tremendous amount of work that has been done on the Traveling Salesman Problem, the TSP is one such problem. If you have an instance of the TSP of practical interest (i.e. it makes a difference to your life if you solve it or not, and it is really a TSP, not the result of some weird set of set of reductions from some other problem), then I bet you the Concorde program of Bill Cook and others will get you a provably optimal solution in a reasonable amount of time. The difference between problems that are hard in the average case, and those that are only hard in the worst case, is really important in cryptography. The knapsack cryptosystem is a good example of this: https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac...
- te_platt 10y ago
  Exactly. A good example would be a set of co-linear points. Even for N=1,000,000 if all the points are at (n,0) on the plane then it's pretty trivial to find the solution.
geofft 10y ago
I think it's famous because it's one of the most easily understandable NP-complete problems: it has a nice, intuitive "word problem" description. 3SAT has no such intuitive description. Even for those of us who understand boolean formulas, there's no particular intuition about how hard 3SAT (and 2SAT) should be. It's a fairly abstract mathematical construct. NP-complete problems admit no polynomial-time solution for every possible answer, and even if they run in more-than-polynomial time, there's no constraint on what those constants look like. Suppose the best algorithm takes 2^n / 2^100000 seconds. That's definitely more than polynomial, but also pretty fast for real-world problem sizes. It turns out that even SAT solvers are also pretty good in practice on real-world-sized problems, to the point where Fedora's and SUSE's dependency solvers (in dnf and zypper, respectively) convert your package dependencies to an instance of SAT and throw it at a generic SAT solver, because that's better-optimized.

jtolmar 10y ago

That Hilbert Curve solution is really handy to know about. If you were writing a game where the player competes with an AI at traveling salesman (Pacman without the ghosts race), a fast 75% optimal algorithm sounds perfect. I think you can do the Hilbert Curve in n log n time by loading all the cities into a quad tree and traversing it in a Hilberty order. Is that the fastest way?

plank 10y ago

I remember the same feeling, a long time ago. I would read the Dutch 'NRC' science page, and be annoyed that they really did not understand the Schrödinger cat problem. Of course, since then I strayed away from my physics career (entering IT with a PhD in physics), and now I can read those same science pages and think, wow they really know their stuff....

skywhopper 10y ago

"I will get my favorite spaghetti meal served on my birthday." In an otherwise run-of-the-mill rant, this struck me as a truly weird, passive, and ungrammatical (to my ear) assertion. The lack of any agent makes me wonder if he's insisted on his parents and then various friends or significant others over the years to serve him this meal. Or does he hire someone to perform this task for him? The lack of the mention of "cooking" and the phrasing "spaghetti meal" make me envision dumping a cold can of Chef Boy-Ar-Dee spaghetti out in a bowl. Just an odd, unrelatable insistence. Weird.

spinlock 10y ago
I smell a startup. Uber for Spagettios.

tater_sent_me 10y ago

It's easy to beat up pop-science. Exhaustively searching for the optimal solution for TSP does take a prohibitive amount of time. Understanding how, why, and coming up with schemes that do allow you to find an optimal solution is what computer scientists have done.

perseusprime11 10y ago

Do they have to know about the Traveling Salesman Problem?

jessaustin 10y ago

This magazine (and its similarly-named rival) sometimes calls to mind Nelson Muntz's comment: "I can think of at least two things wrong with that title."

waldrews 10y ago

Cixin Liu's The Dark Forest has the alien enemy ship solve the traveling salesman problem for a moderate n in real time as a way of demonstrating the aliens' superior level of science. That must upset the original poster almost as much...

SeanDav 10y ago

How does one know one has an optimal solution for the travelling salesman problem? Any experts out there that can explain this, or point to some accessible literature on this?