“American Scientist” Understands Nothing about the Traveling Salesman Problem
mat.tepper.cmu.edu
mat.tepper.cmu.edu
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.
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.
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.
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.
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.
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")
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.
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.
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.
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.
> OP's controversial comment (-50)
> response (+10)
> OP's responds back with evidence or clarification (+100)
where OP was simply misunderstood.
I'll give you a recent example: there's nothing wrong with servers running ad-block detectors and not serving content to people running ad-blockers. It's within their rights. It's not "within their rights" for people to circumvent these and try to see the content anyway.
Since on a technical level the content owner's web server is both serving the content to you at their expense, for which your browser makes a request, and also is specifically serving copyrighted content, and finally on a moral level has created that content at their expense, I consider it absolutely, 100% within their moral, legal, technical, and decent rights to throw up a TOS saying: "Our business model is showing you advertising, and you agree to load and not block ads. Click 'I agree' to proceed". It's in my opinion within their moral, ethical, technical, and legal rights to detect and block people using ad blockers. It's not a technical "arms race" for people installing plugins that let them trick the server into serving them content even though they're not displaying ads, while the server chooses not to display them content. Even if there is NO such click-through TOS being thrown up, the server by running ad-detection algorithms makes this relationship abundantly clear.
I wrote this here: https://news.ycombinator.com/item?id=11458626
All of my contributions were downvoted, which is fine, but people were also extremely rude. They didn't understand my bakery analogy, and focused on something irrelevant, the TOS. (This is like saying the bakery didn't have a sign up saying you couldn't reach behind the counter and take something. I mean, the fact that the server is actively running ad-block detection and wanting not to serve you isn't enough? It's also irrelevant because it takes one line to add that to a TOS so it's not a real response.)
So here is an example of a fine contribution in which my view is correct and HN groupthink is completely wrong.
untog pointed out that my comment was correct by stating "Seems telling that you're getting downvotes but no replies explaining how your comparison is wrong..."
Going forward, of course I will not be using that analogy.. Indeed I won't post on any ad-block related subjects.
Of course, this doesn't mean I don't expect people not to run ad-blockers, just as the existence of copyright doesn't mean I don't expect people to torrent stuff. I just mean that they're not morally in the right, they shouldn't act righteous about it, and servers that refuse to serve people content when those people are running ad blockers are in no way (not even a tiny way) in the wrong.
I'll probably be downvoted for this, I just wanted to give you an example of something that I wouldn't post. I literally wouldn't be posting this now except as an example of something people will downvote.
If sites with paywalls wanted to distribute encrypted PDFs to their customers that would be one thing. But they're using HTML and the whole point of that is that the client renders it. I will always reshape your HTML + requests before I fetch and render it. That's how it works. If you don't like that, this is not the medium for you to engage me in.
Also, ads are grandfathered in, in most people's minds, because they happened before our privacy discussions started. But when you consider the insidious tracking and the anti-anti-tracking measures (how is that not hacking?) going on, they're a hideous technology. If history was different and you just invented internet ads now you'd be called a malware author and privacy abuser (of children!). So it's time public perception catches up with reality and (tracking-capable) ads die a fiery death.
The owners of the server have made it clear that they don't want to serve you content. The principles of fairness and honest dealings say that you should respect those wishes, even if you technically can work around them.
But you haven't done anything to show an obligation, on my part, to view them. You've merely stated how you're so right about there being one.
What the sites are asking for is abusive - to use an open protocol for DRMed content. They're trying to have the benefits without the costs. Well, tough. If they want use DRM - let them use PDFs. Those contain mechanisms to prevent the manipulation of the content.
The web is an accessibility tool, not yet another marketing cesspool.
For example, in hotel industry, you open the fridge for 5seconds, that charges to the bill, and they tell you it has become industry standard everywhere, you'd eventually accept it that they're producing electricity for your service (even just 5 seconds of opening the fridge, and dont touch anything).
I got upvote for simple jokes, but never got upvote for invested comment. I dont understand why, but meh..
First, snark, sarcasm and satire are certainly an effective way to get a point across sometimes (ex:[0] which is currently the most upvoted 'apply hn').
However, it's not always be the way to express an argument. Indeed, your analogy about the bakery isn't even about the moral, ethical, technical, or legal issues of the topic. Any argument that you may have meant to make about ad blocking is belied by your conclusion which is "(how I feel people sound when they talk about their right to use ad blockers over the wishes of the people who the ads would be paying and whose servers are serving the content.)". You made an argument attacking people, not an argument about how adblocking is wrong (regardless of your intent).
Had I read the above when it was originally posted, I likely would have downvoted it. Not because I disagree with you, but because I feel that HN is not a place where character attacks are welcome. Assuming that this is just 'groupthink' (with no other cause) is an error.
As an aside, I find your bakery analogy amusing. There's a bakery in my town that I've frequented many times and it is operated on the honour system. There's no cashier in the bakery and the displays don't have any glass in front of them. You're expected to just grab what you want and drop the cash in the cash box. You know what? People do it! The fact that the bakery owners so obviously demonstrate their trust to their customers engenders a lot of goodwill.
As for ad-blocking? To me it's a simple matter of the right to control my browser and which content it downloads and how that content is displayed. If your site is going to put neon green text on a purple background, I'm going to tell my browser to ignore that so I can read in black and white.
If you want to tell your web server to refuse access to those it deems are blocking ads, that's totally fair. Just as I have the right to control my browser, you have the right to control your server.
As for copyright? I think the whole concept of exclusive ownership of content is dubious. Study some historical literature and see how heavily George R R Martin borrowed from Greek tragedy, for example. It's silly to me that we should claim he's the sole creator and the owner of this story. We stand on the shoulders of giants. Everybody is indebted to society for a great many reasons.
It turns out that, although possibly a virtue when programming, hubris can easily lead you astray if you're outside your field of expertise. Humility is more useful in these situations.
I am sure that this holds true for many other topics; it should give us all pause before we accept statements as true just because they sound agreeable to us, or before we regurgitate opinions whose veracity we're not in a position to verify.
Incidentally, I've also spotted this on the TV show QI, many of whose clever 'facts' are misleading at best or just plain incorrect.
It's Wrong.
It's Correct, and you are mistaken.
It's Correct, but poorly communicated.
PS: This is also far worse on the softer ends of hard science. Diet, Economics, Climate, Astronomy, and Evolution all suffer from studying complex things with limited ability to experiment.
I know this is veering wildly offtopic, but when I see misconceptions about evolution on HN, they're usually not being displayed by people with too rudimentary a science background, it's mostly people with an altogether unscientific background such as creationism or other religious and philosophical ideas that are in conflict with factual information.
> Incidentally, I've also spotted this on the TV show QI, many of whose clever 'facts' are misleading at best or just plain incorrect.
I'm not familiar with that show, but that's a common problem in science journalism now, and it's not even confined to "popular" science anymore either. Maybe it's always been that way, and I just notice it more nowadays.
There is also a lot of the opposite - but just as bad - phenomenon going on: I believe shouting out unreflected gotcha!-style rebuttals to comments has become somewhat of a sport around here, to the point where I sometimes wonder if misunderstanding the original comment was maybe an intentional act.
Some people scan comments looking for specific things that conflict with some narrative they're promoting, usually with regards to a product. They will:
* only reply to comments that are going to be seen by many people, e.g. those near the top, at certain times of the day, within a certain time of being posted
* write the reply in the shortest amount of time
* write a reply that deflects attention away from the original comment, irrespective of whether that reply makes any sense
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.
> 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.
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.”
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...
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).
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.
not quite -- once you have a solution that runs in time X, you no longer need to check any solution that has a sub-component that is known to take longer than time X. So, for example, if you find that going between locations A, C, J, F, P, E, and Q in that order takes longer than your current best whole-map solution, then you no longer have to check any solution of which ACJFPEQ is a subset. You can eliminate whole categories of solutions with a single check, instead of having to test each of them one-by-one.
Agree with lotharbot here. You are as stuck with checking all N! solutions as a sorting algorithm would be. A good TSP algorithm won't, and nor will a sorting algorithm.
Just as sorting has a vast set of solutions, the best of which we can find in guaranteed O(n log n) time, a TSP problem admits an algorithm (branch-and-cut) that does not enumerate N! solutions, and actually a lot fewer.
The tricky part is that branch-and-bound and branch-and-cut algorithms (such as the one developed by Cook et al.) are implicit enumeration schemes, in that are proven to obtain the best solution of the N! without actually visiting all of them.
No, you're not. There is an exact dynamic programming algorithm that takes O(n^2 2^n) time, which is exponential but much smaller than O(n!).
"Every subpath of a path of minimum distance is itself of minimum distance."
[0] https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm
> 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. In fact, I would be really interested in knowing the smallest “real” instance that Concorde cannot solve in, say, one day, on a normal laptop computer.
Note the "provably" before "optimal solution".
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?
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
Let M be the largest distance between any two points in your graph. Add M to the length of every edge. Now the triangle inequality is trivially satisfied and you've got a Metric TSP.
However the "you find a path within a factor of 3/2 of the best possible" guarantee of the Christofides algorithm is much less useful than you might hope because all paths just got a lot longer.
But how do you define "intersecting paths" there?
Basically you are checking for line-plane intersections. A solution should outline a "non-self-intersecting volume".
Also, the hull needn't be convex.
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).
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.
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/
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/
http://sjcomp.com/files/compsci9703.html
I will have to reread it to see if it still makes sense.
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_knapsac...
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.
I believe the point the posted article is making is that reasonable progress has been made against such problems of sizes that seem 'large' in terms of normal human experience, through brute-force computation and clever heuristic tricks. That doesn't mean they don't scale in the expected way or that a true shortcut has been found.
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?
[0]: http://bit-player.org/about-the-author
[1]: https://www.americanscientist.org/authors/detail/brian-hayes
[2]: https://www.americanscientist.org/issues/pub/2015/6/computer...
Any experts out there that can explain this, or point to some accessible literature on this?
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.
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.
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.