> 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.
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.
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.
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.
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.
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.
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.
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!
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")
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.
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.
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.
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.
> 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.
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.
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.
Or alternatively, their score flips from positive, to negative and then to positive (or the opposite) but manages after a while to get an equilibrium and stabilises at 1. I really think some folks must get a little manic when the realise the comment hasn't gone grey...
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.
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.
The whole point of HTML documents is that the client renders them. I vastly prefer web docs because they reflow to my screen, can be decluttered, styled, etc, over PDFs and the like.
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.
There is nothing honest about trying to run DRM over HTML. Serving adds are pissing in a public pool. It might be convent, but it makes things worse for everyone else.
right, you're the only one who is correct in this thread, and the other responses are wrong - and yet my comment explaining this is downvoted. But look at all the noise that was generated in this thread! So, this is actually a fantastic illustration of why on some political or certain controversial issues, when HN groupthink is wrong (such as all the other responses in this thread) it's better not to point out the correct view.
You're both stuck on a nugget of truth - that it's obvious they don't want us blocking ads. Yes, it is.
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.
Probably you'd like to hear this. "Copyright" is in a controversial and heated debate. Corporate evil becomes too rich to start to define what they want. The point of running an ad-blocker is not just that ads are annoying, but i don't want corporate media to get a step further toward absolute power over consumer (which is my side). Knowledge eventually should be free enough.
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..
So I went ahead and read your bakery analogy at the link you provided. I have not previously viewed it.
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.
I'm sorry you got downvoted but I still don't think it should dissuade you from sharing your thoughts. I've been downvoted many times in the past and it's never stopped me.
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.
I've noticed this on HN for genetics- and especially evolution-related topics. Many commenters here confidently state as fact things which turn out to be dead wrong. If your knowledge of evolution is limited to having read 'The Selfish Gene', you should be aware that you likely carry several misconceptions and also have many large gaps in your knowledge.
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.
There are three options when you disagree with something on on HN.
It's Wrong.
It's Correct, and you are mistaken.
It's Correct, but poorly communicated.
IMO, the poorly communicated issue shows up far more than most people assume. I have seen several discussion between two experts go X, that's wrong Y, that's not true X(1)... then after 10 posts they end up agreeing that X ~= Y if Z.
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.
> If your knowledge of evolution is limited to having read 'The Selfish Gene', you should be aware that you likely carry several misconceptions
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.
> For several domains I know something about, the comments here are painfully misguided and just bad
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.
> 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
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.
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.
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.
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.
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.
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
“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.”
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...
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).
> Nobody compares all N! permutation for sorting, and nobody checks all N! tours when solving a TSP.
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.
If you really want the single best solution, you're stuck with checking all N! solutions.
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.
The linked post mentions a previous post [1] where he mentions that proving you have the optimal path doesn't always require N! cost:
> 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.
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.
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.
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".
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?
>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.
There's a more fundamental issue here-- when talking about approximation algorithms reductions don't necessarily preserve approximation ratios. If you take a standard TSP instance with optimal tour length C and add the largest distance between two points M to every edge, you get a new (metric) TSP with optimal tour length C + nM, where n is the number of nodes of the graph. Applying the Christofides algorithm to this new metric TSP instance can only guarantee a tour of length 1.5C + 1.5nM, and when you subtract M from every edge again to get a tour in the original TSP instance, this scheme will return a tour of length at most 1.5C + .5nM, a bound which is provably tight. This is a terrible approximate solution, since if the largest two-node distance is O(C) (for example), the approximation obtained has value O(n)C-- a monstrously bad O(n) approximation!
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.
I'm no expert, but I don't think the "metric" in "Metric TSP problem" means "embeddable in a 2-D space." If you pick random points in a 500-dimensional space, the graph is metric.
You should be able to "wrap a hull" around all the points. If there is no hull that can be wrapped without intersecting a path segment, the path is not a solution.
Basically you are checking for line-plane intersections. A solution should outline a "non-self-intersecting volume".
Defining a convex hull in a 100-dimensional space requires 101 points. You can easily have a scenario where the only available "convex hull" is the one that contains the entire graph. In fact, I'm sure that a "randomly chosen" metric graph will be of this variety.
> 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).
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/
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.
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.
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.
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?
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_knapsac...
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.
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.
Each NP-complete problem is in fact a family of problems. In the sense that you could compute an optimal sales route between a small number of cities or optimally pack a very small knapsack in your head.
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.
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?
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....
"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.
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."
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...
101 comments
[ 3.0 ms ] story [ 61.0 ms ] threadI 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.
[0] - https://news.ycombinator.com/item?id=11441480
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.
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.
http://sjcomp.com/files/compsci9703.html
I will have to reread it to see if it still makes sense.
[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...
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.
> 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".
1: http://mat.tepper.cmu.edu/blog/?p=6995
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).
http://people.idsia.ch/~luca/acs-bio97.pdf
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/
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.
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?
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.
Understanding how, why, and coming up with schemes that do allow you to find an optimal solution is what computer scientists have done.
Any experts out there that can explain this, or point to some accessible literature on this?