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.
I would have to say 3-SAT. Simply because it sits at the root of most NP proofs and nearly any other NP problem can be reduced to it.
Good book BTW. Its still used in most universities for teaching advanced algorithms and algorithm theory.
I say this often and I think it applies here rather well: The best solution to any problem is avoiding having that problem (not avoiding solving it) in the first place.
Wow. Just wow.
Jeff, why did you post about a subject about which you know so little? Infact, why did you even link to a book you didn’t read? I don’t understand how you can be in a position to recommend it at all.
Regarding not being satisfied by approximate solutions, I like to point out that the original problem was itself an approximation. If a salesman really wants to visit a bunch of cities, there are lots of little things that go into determining what really is the best route that are not part of the simply-stated computer science problem – avoiding roads with construction, not driving through major cities at rush hour, etc. – and so your solution that’s within 2% of optimal may be just as good as the exact solution at solving the real problem.