Have you ever heard a software engineer refer to a problem as "NP-complete"? That's fancy computer science jargon shorthand for "incredibly hard":
@M Wow. You really know how to take the bait in every sense of the phrase!
Articles like these are exactly why I read Coding Horror. I get a brief introduction to a subject I will find interesting, that I ought to be aware of the existence of, or both. I also get a little humour, and not so much as a trace of condescension about my lack of abilities or knowledge.
It’s never occurred to me, ever, to just take Jeff’s word for anything. Why would I? No subject that I find interesting is likely to be completely exposed by a few paragraphs, however accurate or well written, especially when a substantial amount of the writing is dedicated as it is to sarcasm, memes, or humourous links. Single-sourcing my learning is unlikely to be helpful either, so I never count on a single source, no matter the level of expertise involved.
Now I have a starting point for any research I care to conduct, a few terms that I can now spell properly, and a useful working definition of the subject at hand. That’s right, not a correct definition; it doesn’t need to be absolutely correct to be partially useful. I can also count on Jeff’s unstoppable sense of self-promotion to require him to keep an eye out for humourous or light updates in future posts , so he can self-link. I don’t have to keep a scan out for developments if I don’t want a deep understanding of the subject.
Just to be clear, it is cheating, if you are the kind of person who believes that every program you write must be totally optimized right out of the gate. Where would Jeff get the idea that a substantial number of his readers are like that, I wonder?
Jeff rocks. His blog is wonderful, informative, and entertaining.
M is an anonymous coward.
Keep it up Jeff.
@Dustman: Thanks, you just saved me a LOT of time writing to make the same points but not as well. I’m a CS grad, and still got something useful from the post: a book recommendation. Thanks, Jeff.
Wouldn’t an optimal solution fall under the realm of premature optimisation? Shouldn’t 2-3% off optimal be fine unless profiling determined otherwise?
You’re confusing micro-optimisations with algorithmic complexity. Selecting the right algorithm is a very different thing from obscuring your code by trying to be clever and fast.
@Jonathan: The transformations that convert an instance of one NP-complete problem into another aren’t necessarily (and typically aren’t) approximation-preserving. Similarly, a heuristic that works well for problem A often won’t work well on an instance of problem B transformed into an instance of problem A.
Dan –
I agree that M is being a bit of an asshole, but I startled a bit when I read that NP-complete was a know it when I see it situation. It’s a precise statement of fact, which is contrary to fact. In other words, it’s WRONG.
I really don’t see what you’re trying to say. The characteristics of a problem that make it NP complete are completely and unambiguously defined – the definition is the same as the definition of NP-complete. What sort of characteristics are you looking for, by way of analogy?
Problem: people.
Solution: hammer.
I think Jeff’s writings regarding hardware are his best.
You would be kind of naive to not think that there is a psychological plan to Jeff’s posts: regular (which may limit his research), self linking, Amazon links, designed to get fan-boys typing and pulse rate up.
Jeff is wrong or incomplete or addressing issues he’s not completely familiar with. If you have read this blog for a number of years then you know in your heart that it has become somewhat unclean.
For me, spreading ignorance (or bad information due to ignorance) is an issue.
If you are gonna talk about subject X, make sure you know subject X, well enough to talk about it. At least, make sure that you are not making gross errors about subject X. Is it really too much to ask?
It bothers me on both the practical level and as a matter of principle.
I’ve been working as a professional programmer for years, and I’ve encountered many without basic scientific background. And that’s FINE! Not everyone needs it, or wants it. But then these people read a blog post, and it sounds right, so they believe it. After all, they lack the knowledge to figure out which parts are true and which are don’t. That’s why they are reading the blog!
And they learn stuff that is WRONG. And then they are going to implement this stuff, and argue about it, and generally BELIEVE that anything having to do with CS is either unpractical or is easily enough learned in 30 minutes of reading.
And then I have to work with these people, and manage them! They have no grasp of how much they simply don’t KNOW. And at some point, their knowledge simply ain’t gonna cut it. And they are going to argue with me, or write me off as a user of fancy computer science jargon. I mean, it’s just register allocation, right? How hard could it be? It’s only BSP tree optimization, let’s just check all the options!
So I am trying to combat this ignorance for practical, selfish reasons. Programmers need to understand the problems they work on. They need to understand when they are out of their depths, and its time to hit the books, or call someone who knows. Or reject that project, or bump up the cost and time estimate. At least map out the areas of your understanding, so you’ll know when you’re on treacherous ground.
The other reason is a matter of principle. Ignorance is pretty bad, and I reject mediocrity for its own sake.
In less fancy terms, if you are writing technical posts, get the technical details RIGHT! Isn’t that a given? But apparently I am an asshole for pointing it out 
For the person who asked, the reasons I read Jeff’s posts are two:
a) Jeff often finds interesting links. I sometimes only skim through what he writes, looking for the links.
b) On occasion like this, I have a chance to make my contribution to education. Maybe help some of the people who would otherwise be misinformed, by pointing out mistakes. People that some day I might work with. I’d rather their eyes don’t glaze over when I mention fancy computer science jargon.
@Swami: calling me an anonymous coward is fine, and perhaps far from the truth, but is also an ad hominem argument.
Want to have some fun with similar problems? Go give Project Euler a shot: http://projecteuler.net/
Some of the last ones will drive you crazy! .
I don’t know if this is considered an NP-Complete problem, but the algorithm I’m still still trying to find a solution to is comparing a data list problem.
Given a table(s) with no primary key or true consistency
Sorry, I guess I should have put a smiley face next to this comment to convey my (poor) humour:
Wouldn’t an optimal solution fall under the realm of premature optimisation? Shouldn’t 2-3% off optimal be fine unless profiling determined otherwise? [hehe]
Better?
@M
But then these people read a blog post, and it sounds right, so they believe it. After all, they lack the knowledge to figure out which parts are true and which are don’t. That’s why they are reading the blog!
I’m a non-scientific person, of the type you allude to. I don’t read this blog as an insight to all things CS. I read this blog for its entertainment value and as an introduction to areas I may otherwise not have come across. Is Jeff responsible for mine and thousands of others learning habits? It is MY job to research areas that I may be implementing.
Further, Jeff has ALWAYS stated not to take his word verbatim. He uses the ‘shock and awe’ method. If people are in a position where they need to analyse NP-Complete problems, do you think their sole reference would be here?
Once I got to uni I was angry at my high school teachers for teaching me ‘incorrect’ definitions. Once I hit third year uni, I was thankful to my high school teachers for not burdening me with unnecessay complexity until it was required.
Finally - a blog post exists for the author to speak about whatever they want to. That people subscribe is their business. I don’t believe there is any responsibility that comes with being a successful blogger. You have no right to tell Jeff he may not speak about something. The comments are here to point out inconsistencies. And if the quality of the post is in question (or that of the entire blog) people will stop reading. This, Jeff has also explained previously.
In summary, M - get off your high horse and write a blog of your own, then direct those that require greater understanding to yours.
Please revise your comment NP-complete problems are like hardcore pornography. Nobody can define what makes a problem NP-complete, exactly, but you’ll know it when you see it. That’s plainly wrong.
How is it wrong?
–
http://max.cs.kzoo.edu/~kschultz/CS510/ClassPresentations/NPCartoons.html
The theory of NP-completeness provides many straightforward techniques for proving that a given problem is just as hard as a large number of other problems that are widely recognize as being difficult and that have been confounding the experts for years. Armed with these techniques, you might be able to prove that the bandersnatch problem is NP-complete and march into your boss’s office and announce: I can’t find an efficient algorithm, but neither can all these famous people.
–
I guess I make a distinction between reducing problem to another known NP-complete problem and proving a problem is NP-complete. Apparently we can’t prove anything is NP-complete, we can only throw a wall of experts at it and see them all fail.
So, a NP-complete problem is not mathematically proven, it’s one that no experts can solve, eg, I’ll know it when I see it.
Or more specifically we’ll know it when lots of experts have seen it, tried, and failed.
Is this wrong?
I write video games and I ‘cheat’ all the time. As long as the results look the same the only thing important to me is how fast can I get those results?
NP - Complete is a mathematical term. I think it should stand for Nobel Prize Completely in the bag! Shame mathematicians can’t get one. Instead they have to be happy with a Fields medal (if they’re under 40)
I’m not really bothered about nit picking myself and I believe that absolute answers are seldom necessary. That’s the difference between the philosophy of Maths (pure) and realistic Maths (applied). No one cares what the billionth digit of PI is. It would just be fun to be able to know what it is in an instant if we wanted to.
I suspect that some questions themselves are actually flawed. It’s a bit like the answer to life the Universe and Everything being 42. Unless the question is understood the answer means nothing.
There is no absolute answer to PI. There never can be in decimal terms. Approximations are what survival is all about.
With the travelling salesman; who says there is ‘the quickest route’ when there might be 100 routes of exactly the same length. Also where does the salesman start? That is not mentioned in the original question, also the layout of the towns, what if they were all in a straight line? Start at one end and work to the other etc… So I believe the question is flawed in this sense.
I think the words ‘cunning approximation’ might pacify the opinions of the masses instead of ‘cheat’
Like the article though.
Can I also mention that I dislike the idea of the Turing test? Why should a computer try to pass itself off as a human? This is a silly test. A computer is a computer and should do what they are good at.
Do we have a test whereby a human has to pass itself off as a computer? No.
Is there a test whereby an apple has to pass itself off as a banana? No.
Alan Turing may have been a genius, but some times they can come out with some pretty stupid stuff, make mistakes and come up with pointless exercises. If a Philosopher wants to spend the rest of their life pointlessly attempting to extrapilate meaning from an inane and misguided question - let them.
My favourite NP-complete cheat is Ant Colony Optimisation. It’s great: intuitive and interesting, if a little difficult to implement.
Thought I’d just add that there are still at least 21 Nondeterministic Polynomial questions to solve and plenty of money to make if anyone fancies having a go at them
Jeff Atwood:
All you who are making out the whole issue of NP-Complete and NP versus P to be just jibber jabber and practical answers are what people really care about don’t really understand the issues involved. I mean, surely, you must realize if you certain problems (like the RSA problem) are able to be solved efficiently then most cryptographic algorithms are basically useless right? How’s that for practical?.. ::shrugs::
Jeff you have one thing wrong there. You can prove NP-completeness, thats what Cook’s Theorem comes down to. What you can’t prove is that there is no way to solve an NP-complete problem in polynomial time. We assume there isn’t, because a lot of intelligent people have been looking very hard and haven’t found one. Now if someone did, every NP-complete problem would still be NP complete, they just wouldnt be difficult anymore.