programming and human factors
by Jeff Atwood
Have you ever heard a software engineer refer to a problem as "NP-complete"? That's fancy computer science jargon shorthand for "incredibly hard":
The most notable characteristic of NP-complete problems is that no fast solution to them is known; that is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a result, the time required to solve even moderately large versions of many of these problems easily reaches into the billions or trillions of years, using any amount of computing power available today. As a consequence, determining whether or not it is possible to solve these problems quickly is one of the principal unsolved problems in Computer Science today.While a method for computing the solutions to NP-complete problems using a reasonable amount of time remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. An expert programmer should be able to recognize an NP-complete problem so that he or she does not unknowingly waste time trying to solve a problem which so far has eluded generations of computer scientists.
You do want to be an expert programmer, don't you? Of course you do!
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. Just this once, I'll refrain from my usual practice of inserting images to illustrate my point.
(Update: I was shooting for a poetic allusion to the P=NP problem here but based on the comments this is confusing and arguably incorrect. So I'll redact this sentence. Instead, I point you to this P=NP poll (pdf); read the comments from CS professors (including Knuth) to get an idea of how realistic this might be.)
Instead, I'll recommend a book Anthony Scian recommended to me: Computers and Intractability: A Guide to the Theory of NP-Completeness.
Like all the software engineering books I recommend, this book has a timeless quality. It was originally published in 1979, a shining testament to smart people attacking truly difficult problems in computer science: "I can't find an efficient algorithm, but neither can all these famous people."
So how many problems are NP-complete? Lots.
Even if you're a layman, you might have experienced NP-Completeness in the form of Minesweeper, as Ian Stewart explains. But for programmers, I'd argue the most well known NP-completeness problem is the travelling salesman problem.
Given a number of cities and the costs of travelling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?
The brute-force solution -- trying every possible permutation between the cities -- might work for a very small network of cities, but this quickly becomes untenable. Even if we were to use theoretical CPUs our children might own, or our children's children. What's worse, every other algorithm we come up with to find an optimal path for the salesman has the same problem. That's the common characteristic of NP-complete problems: they are exercises in heuristics and approximation, as illustrated by this xkcd cartoon:
What do expert programmers do when faced by an intractable problem? They cheat. And so should you! Indeed, some of the modern approximations for the Travelling Salesman Problem are remarkably effective.
Various approximation algorithms, which quickly yield good solutions with high probability, have been devised. Modern methods can find solutions for extremely large problems (millions of cities) within a reasonable time, with a high probability of being just 2-3% away from the optimal solution.
Unfortunately, not all NP-complete problems have good approximations. But for those that do, I have to wonder: if we can get so close to an optimal solution by cheating, does it really matter if there's no known algorithm to produce the optimal solution? If I've learned nothing else from NP-complete problems, I've learned this: sometimes coming up with clever cheats can be more interesting than searching in vain for the perfect solution.
Consider the First Fit Decreasing algorithm for the NP-complete Bin Packing problem . It's not perfect, but it's incredibly simple and fast. The algorithm is so simple, in fact, it is regularly demonstrated at time management seminars. Oh, and it guarantees that you will get within 22% of the perfect solution every time. Not bad for a lousy cheat.
So what's your favorite NP-complete cheat?
@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?
Dustman on November 15, 2008 1:05 AMJeff rocks. His blog is wonderful, informative, and entertaining.
M is an anonymous coward.
Keep it up Jeff.
Swami Atma on November 15, 2008 1:37 AM@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.
A. L. Flanagan on November 15, 2008 2:02 AMWouldn'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.
[ICR] on November 15, 2008 2:30 AM@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.
Joe Ganley on November 15, 2008 2:56 AMDan --
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?
Ens on November 15, 2008 2:57 AMProblem: people.
Solution: hammer.
dnm on November 15, 2008 3:16 AMI 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.
M on November 15, 2008 3:37 AMWant 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! .
Mitch on November 15, 2008 3:48 AMI 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
---------------------------------------------
Thomas Smith 123 Any St Suite 1 Dayton 45424
Tom Smith 123 Any St Apt 1 Huber Heights 45424
Roberta Smith 123 Any St Apt 2 Huber Heights 45424
Bobby Smith 123 Any St Apt 2 Dayton 45424
ABC Realty 123 Any St Apt 1 Dayton 45424
---------------------------------------------
Try to de-duplicate and/or assign a consistent reference to the data programmatically has always been a nightmare.
The other problem I've run into is capitalization of proper names. Easy to do for a human, but tell a computer to do it.
Jim P. on November 15, 2008 4:07 AMSorry, 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.
`Josh on November 15, 2008 5:28 AMPlease 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?
Jeff Atwood on November 15, 2008 5:43 AMI 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.
:)
Sci-Fi Si on November 15, 2008 5:47 AMMy favourite NP-complete cheat is Ant Colony Optimisation. It's great: intuitive and interesting, if a little difficult to implement.
Dom on November 15, 2008 5:51 AMThought 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
:)
Sci-Fi Si on November 15, 2008 5:54 AMJeff Atwood:
------------------------
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?
----------
No Jeff, with all due respect, this is completely wrong. There is no mathematical problem called The NP-Complete Problem. There are certain problems are NP-Complete. You are confusing this with the P=NP Problem.
You JUST wrote that we *can't* prove that a problem is NP-Complete that is completely false. We *very well* know how to prove a problem is NP-Complete. You really need to go through some introductory texts first. It is not like Well, it's like porn; I know it when I see it.
The issue is with P=NP. Also, it's not cheating and its not as if Computer Scientists are trying in vain to find optimal solutions. That's just silly. Saying that no experts can solve it so I know it when I see it reveals a fundamental lack of understanding in the theory. If you want to talk about what is practically done or something like that then you can say something about how in many cases we proceed as if P != NP; however there is no proof of *that*. However, we can very well prove that problems are NP-Complete.
The bit you quoted:
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.
All that is saying is that you may find some new problems which are NP-Complete but it is also very likely that those problems can be restated in the form of a well known NP-Complete problem (probably one of Karps 21 NP-Complete problems).
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::
Charles on November 15, 2008 6:13 AMJeff 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.
H on November 15, 2008 6:21 AMI 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.
Blair on November 15, 2008 6:39 AMI 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.
Calvin Spealman on November 15, 2008 6:55 AMWow. 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.
John on November 15, 2008 6:57 AMIf you look carefully you will see that I'm an apple.
However, there is no way of working out how long it will take you to see that I am an apple.
I will say between 3 days to 17.2 years depending on how many degrees of Kevin Bacon there are between us
Banana on November 15, 2008 7:06 AMapproaches that use evolution in one way or another are pretty damned good. for the traveling salesman problem you could use a generic algorithm, for example. they're really fun programs to write too!
nanreh on November 15, 2008 7:19 AMUp Up Down Down Left Right Left Right B A Select Start
AAAARGH! So... many... inaccuracies... must... bleach... brain...
By the ancient Hynerian gods, Jeff, please never ever write about computer science again. Seriously.
Yes, maybe you got your main point across, but you could just have easily explain it all to laymen without making useless mistakes on the way. Well, *someone* could have gotten it right. It is evident that you couldn't... Or didn't even try.
The two most annoying are probably calling approximations cheats, and your obvious lack of research into what NP-complete means (or even, what it IS).
Approximation algorithms and their bounds don't just appear out of thin air. They are more often than not invented, researched, proven correct, and upper-bounded by the same fancy computer scientists studying intractable problems. They are often quite a bit harder to reason about than the obvious (but slow) optimal solutions. Calling them cheats is like calling dynamic programming a cheat because it just uses more memory.
Regarding NP-complete, it is not only a fancy computer science jargon shorthand for incredibly hard. In the same vein, gravity is not a fancy physics jargon for things fall down. There's a meaning behind the term, there's theory. Thank you for trivializing complexity and computability.
Nobody can define what makes a problem NP-complete, exactly,? Perhaps *you* can't. After all, it's just fancy jargon, isn't it?
For those reading my rant this far, here's a quick informal definition from the National Institute of Standards and Technology:
A problem is in the NP-complete class if answers can be verified quickly (polynomial time in length of input), and quick (polynomial time again) algorithm to solve this problem can be used to solve all other NP problems quickly (this is called reduction).
You can also find it in the top of wikipedia's page on NP-complete here http://en.wikipedia.org/wiki/Np_complete .
When doing the traveling salesman problem; do you include layovers as being a city that he/she visits? :P
Suroot on November 15, 2008 7:41 AMLike M said (but less abrasively), there's a concrete definition of what NP-Complete means. It's mathy, but that just means it's a CS thing instead of a programming thing.
I don't mind calling approximations cheats, whatever gets you through the day.
Bill Weiss on November 15, 2008 7:51 AMJeff:
As many people have pointed out, you're completely wrong with saying nobody knows what NP-complete is. NP-completeness is perfectly clear and actually has a definition (just look on Wikipedia and you'll see it).
P is the class of problems that can be solved in polynomial type. For example, mergesort is O(nlogn) which is polynomial, therefore mergesort is in P.
NP means non-deterministic polynomial time, which means that given a problem and a solution to that problem, you can verify whether the solution is correct for the problem in polynomial time (which means if we have some kind of quantum computer that is capable of doing all possibilities simultaneously, then we can solve any NP problem in polynomial time).
An NP-complete problem is a problem that is more difficult or as difficult as any problem in NP. We have proven many problems are NP-complete - look at SAT and reducibility on Wikipedia and you can see for yourself.
The problem (as some people have pointed out) is proving that P is the same set as NP. Computer scientists haven't been able to prove this right or wrong. Don't get this confused with people not knowing what NP-complete is.
Also keep in mind that NP-complete isn't as hard as it gets. There are complexity classes that are harder than NP like NEXPTIME.
Rob on November 15, 2008 7:54 AMNP-Complete is perhaps the most non-intuitive name for a very very hard problem!
Wouldn't an optimal solution fall under the realm of premature optimisation? Shouldn't 2-3% off optimal be fine unless profiling determined otherwise?
It amazes me that the realm of computers, somewhat uniquely, is subject to the constraints of pure efficiency. For thousands of years we have done things the slow way then when we finally have a method of solving a problem 1 million times faster, we're expected to do it 1.001 times faster. Baffles the mind.
Take for instance, traffic lights. The most horribly inefficient system in existance today - affecting millions of people and I'd argue costing millions of dollars annually in inefficiency. Work on solving that problem before worrying about saving that poor salesman $100 in gas money.
`Josh on November 15, 2008 7:55 AMI don't think Jeff ever claimed to be an expert in the complexity field, or whatever field of CS this falls under... So try to be a little nicer in your smarter-than-thou critiques.
the porn quote---
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.
----
I don't think Jeff (correct me if wrong) is talking to people who have studied the subject... he's talking to the SOFTWARE ENGINEERS (not all software writers are computer scientists, you egocentric SOBs). He is talking to the people who replied thinking the traveling salesman problem is about a salesman.
A software engineer does not need to be able to memorize a list of infinite manifestations of NP-Complete problems (TSP being an optimal network path vs an actual salesman, vs google maps vs how much wood could a wood chuck chuck). A software engineer need only to have a 'spider-sense' about these problems and the know-how to recognize or prove that his/her problem is NP-Complete.
I think it's funny that this article is under such fire...
Jeff may not be able to write a scholarly article on NP-Completeness... but he knows it when he sees it. Isn't that the point of this?
3D Software Rendering
Hoffmann on November 15, 2008 8:33 AM+1 for @M and @Bill Weiss: There are well-accepted terms of art for these; please don't call them cheats. Also, you failed to communicate the distinction between an approximation algorithm and a heuristic. The latter is an algorithm that works well in practice but isn't guaranteed to do so, while an approximation algorithm has a specific bound on how nearly optimal its answers are guaranteed to be. (There are also randomized approximation algorithms, which provably meet a bound from optimality with a specific probability, often dependent on specific characteristics of the input.)
However, I'll agree with the notion that every software engineer should understand NP-completeness at least well enough to recognize the possibility that he/she is encountering it.
Joe Ganley on November 15, 2008 8:42 AMJohn:
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 [...]-- avoiding roads with construction, not driving through major cities at rush hour, etc. ...
Thats why people invented weighted graphs.
Josh:
NP-Complete is perhaps the most non-intuitive name for a very very hard problem!
Wouldn't an optimal solution fall under the realm of premature optimisation? Shouldn't 2-3% off optimal be fine unless profiling determined otherwise?
It might not be intuitive, but it is rather logical when you know the theory behind it.
What the hell are you talking about? Profiling refers to running time, 2-3% off refers to optimality. If you already know that your problem is NP-complete and your instance sufficiently large, you won't have to do profiling (which will be rather unsuccessful anyway). But if you don't get that TSP is just an analogy to describe a kind of graph problem, which can come up in totally different contexts, you're a lost cause anyway.
Jeff, I have to concede with M here. Maybe you managed to give a somewhat perverted introduction to the topic.
But this one makes me cringe: Nobody can define what makes a problem NP-complete, exactly, but you'll know it when you see it.
Do you really think that? Do you think that thousands of papers and hundreds of books have been written about a topic, which is not clearly defined and that in theoretical computer science?
I'm the first to admit, that it might be difficult, if not impossible to define NP-completeness in a blog post and I would have been really amazed if you had pulled that off. But, blatantly lying and saying it can't be defined was the worst thing you could have done.
H on November 15, 2008 9:11 AMWith respect, M, Jeff did not say that there is no definition of the term NP-Complete. He clearly knows what the term means, and even links to the Wikipedia article you cite. What he said is there is no way to define the characteristics of a problem that make them NP complete. That's a much more interesting problem, and he's right. We don't have an a priori way to tell which problems are going to be NP Complete, though we can recognize when a specific problem is. Its worth reading Jeff's wording carefully, as he's usually quite precise.
There's really no need to be so aggressive and patronizing. Especially if you aren't correct.
Dan
Dan on November 15, 2008 9:15 AMNobody can define what makes a problem NP-complete, exactly, but you'll know it when you see it.
I think what Jeff means is that nobody can define what makes a particular problem belong to NP, but not P. Of course, we don't know if any problems actually do satisfy this, but some (like the traveling goofball) seem to.
Eam on November 15, 2008 9:22 AM@Chees0rz:
[quote]
I don't think Jeff (correct me if wrong) is talking to people who have studied the subject... he's talking to the SOFTWARE ENGINEERS (not all software writers are computer scientists, you egocentric SOBs). He is talking to the people who replied thinking the traveling salesman problem is about a salesman.
[/quote]
Perhaps your definition of a software engineer differs from mine. I'd expect any decent SE to have a fundamental grasp of algorithmic complexity -- to the point that they can discuss problems with different complexity classes and tell me why a given problem is very hard. I'd also expect a software engineer to know that the TSP has very little to do with salesmen.
I suggest that anyone who cannot deal with (or at least be able to learn) such theory is in the wrong profession. Computers are hard. Programming is hard. In order to be proficient programmers we need to understand the nature of that hardness lest we make stupid mistakes that cause our software to fail spectacularly.
I don't think any of this is unrealistic. In Australia at least, Software Engineering is just as rigorous in these areas as Computer Science and nothing being discussed in this article or the posts that follow it are beyond undergraduate level education.
Daniel on November 15, 2008 9:40 AMTraveling Salesman is not NP-Complete, the decision variant is.
http://en.wikipedia.org/wiki/Travelling_salesman_problem#NP-hardness
I sortof expected little mistakes like that, though. Algorithmic complexity can be very counter-intuitive. For example, if you have to decide colorability on a planar graph:
2-coloring: P
3-coloring: NP-Complete
4-coloring: constant time [4-color theorem]
For those who try to defend the author, we are not blaming him because he is being brief. We are blaming him because he is WRONG.
NP Completeness is a term that can be easily defined, but he is taking a wrong approach. NP is NOT about a problem being hard. It is about the fast verification of a given solution. So in short, NP completeness only has two aspects:
1) fast verification of a given solution
2) If you can solve one NPC problem quickly, you can solve them all quickly.
I don't think this is that much more complicated that what the author said, but this is the correct explanation.
Also, saying that NPC problems can be spotted by expert programmer is completely and utterly false. One excellent example is primality check. For many many years people believe that to test whether a given integer is prime is NPC, WRONG. With the discovery of AKS primality check in 2002, we know that actually primality check is actually in P. Even the best mathematicans/ programmers wouldn't have known before that.
Freddy on November 15, 2008 10:14 AMThat might be what Jeff wanted to say, however there is a strong definition of NP-completeness (a language L is part of NP and all other languages in NP are polynomial time reducible to L). As all problems in P are part of NP, this remains the same even if P=NP. In that case it won't be very interesting, as all problems in P, except always accepting and never accepting are P-complete, but it is still a valid definition.
H on November 15, 2008 10:16 AMStrilanc,
if you start with Jeff not mentioning that he talks about decision problems, you might as well mention that he didn't state what type of reduction he is talking about.
@dan:
I've set it before. Jeff's MO is the google expert MO (he calls it just-in-time learning). It may be fine if you're just trying to solve this or that problem and get on with your work. But if you're gonna talk about something, you had better do the research. And Jeff seldom does.
Obviously Jeff puts in considerable time in *writing* his blog posts. I appreciate that. Is it that hard to spend more minutes for *researching* them?
Or here's an idea! Don't talk about things that you clearly DON'T know about. Reading Wikipedia does not make one a domain expert, and is definitely not enough to start explaining this to others.
Every single time Jeff talks about something I know about, he make many small but not insignificant errors, betraying his ignorance on the subjects. Sometimes Jeff makes gross errors. The kind of errors that anyone who has a little bit of knowledge in that area would know.
It makes me wonder how much of what Jeff says about stuff I don't know about, is a mistake.
Also, trivializing the work of hundreds of computer scientists is extremely condescending. I actually avoided calling it what it is, in my previous post.
How can Jeff, with his 30 minutes of reading Wikipedia, claim that no one can define what makes a problem NP-complete?
And calling something 'fancy computer science jargon shorthand for incredibly hard' is not only condescending, it's down right insulting, when it comes from someone who very obviously don't know what their talking about.
My point? Such articles (read back a bit, this is not an isoladed incident) are superficial and shallow, poorly researched pieces.
I don't think it was Jeff's intention, but they promote and ENCOURAGE the notion that programmers don't need to study CS at all, that it's just a bunch of B.S.
I mean, why study intractable problems when we can cheat?
And like I said, it's insulting. I don't insult Jeff's work as a web programmer. I know NOTHING about web programming. I don't write about web programming in such manner.
Dan, We don't have an a priori way to tell which problems are going to be NP Complete, though we can recognize when a specific problem is
That's a great sentence. Very clear. But that's totally not what Jeff said. Again, I encourage you to read back through the archives, on posts dealing with subjects bordering on CS. Jeff is often wrong on the basic details, and you can read the comments and see him being corrected time and again.
Wow, these comments have gotten pretty nasty.
I think what's coming out more than anything is evidence of the growing animosity between computer science (theory) and software development (practice).
@M: It's insulting? How many computer scientists have I heard in the past week imply this analogy:
computer science : mechanical engineer :: programmer : auto mechanic
I've known brilliant head-in-the-clouds computer scientists (PhDs and all) that write code at a rate of 5 lines per month (with comments).
Until both sides start respecting each other as completely distinct yet dependent professions, this kind of thing will be par for the course.
Anonyous Coward on November 15, 2008 11:06 AMThis is my first post to this discussion, since I just saw the post. Well, I am really curious why people are 'defending' Jeff.
Nobody here is trying to show off.
The information presented in the blog post is plain wrong, and therefore misleading. I am not going to discuss the relevant topics here (i.e., NP-completeness and approximation algorithms - called 'cheat's in the blog post). This is not a matter of attack or defense, but maybe an opportunity for Jeff to do some self-criticism.
At various posts, I disagree with Jeff, but most of the posts are on very subjective topics, and since there is no objective metric, argument is time spent for nothing. But disagreement is not bad, I am sure in some of the topics Jeff's are more accurate than my thoughts, and in some vice versa.
The worrying part about the post is not only its inaccuracy, but its reflection on the credibility of the author himself. At most times, when I am ignorant on a topic he posts on such as 3D cards, I took what he said for granted - not totally granted, but with high confidence I should say. This is not true from today on, because today he posted on a topic that I am very knowledgeable about, and the information is wrong, which forces me automatically to degrade his credibility on the other posts from today on.
But I hope that the comments on this blog post will at least force Jeff to reconsider his posting strategy.
Jeff: I think you are a good writer, and I don't have to tell you this, because you make your life from blogging which says enough. In any case, I think you should stick to the following basic principles:
* Do not post about something you don't know as if you have an idea about it: Posting about something you don't know is fine unless you make it absolutely clear you don't know it, want to learn more about it, or asking the reader's for assistance and comments.
* Do not give references to text you haven't read unless you make it clear you haven't read them: If you had read the first 2 chapters of Garey Johnson, you'd not have written this post.
I suggest that you retract this post, or the misinformation propagated will be your fault. I think one of the readers can make a guest post about the topic, which will be informative to the people who don't know the topic.
tuncay on November 15, 2008 11:19 AMTo all of the current posts detractors, if you dislike this site so much, why on earth do you even bother to read it? Does it make you feel superior to tear down and trash someone elses observations and comments?
On a somewhat unrelated note, I consider the orange CAPTCHA system that Jeff setup was brilliant, especially after reading his explanation of it.
I feel there is an IQ test somewhere regarding peoples complaints against it...
Davide on November 15, 2008 11:22 AMHow much wood would a woodchuck chuck, if a...
Reviculous on November 15, 2008 11:51 AMNobody can define what makes a problem NP-complete, exactly, but you'll know it when you see it.
Is this a joke?
Peter Davis on November 15, 2008 12:25 PMAccusing Atwood of not explaining NP-completeness well enough here is like expecting your friendly college science professor to explain the mathematical and cosmological underpinnings of E=MC2 in 1000 words or less.
Or when the kindergarten teacher doesn't explain the Greco-Roman-Arabic derivation of the letters of the alphabet to his four-year-olds, do you start ranting and raving in his face, spittle flying, cursing his stupidity?
The piece was (obviously) an attempt to take a very difficult subject and make it palatable. I'd say it succeeded. It's a pale and weak sort of ego that would find anything offensive here.
Just my .02.
James Devlin on November 15, 2008 12:27 PMI was wondering about the not having approximations for all NP-complete problems. The thing that is getting me is I thought that part of the definition of being in the NP-complete set is that a problem in the set is isomorphic with every other problem in the set. ( That is why proving that p=np or the inverse for one problem proves it for all of the problems. ) Given that why is it that we can not us a approximation for one on any of the others? Am I really confused about something here?
-Jonathan
Jonathan Moore on November 15, 2008 12:28 PMa href=http://en.wikipedia.org/wiki/Graph_theoryhttp://en.wikipedia.org/wiki/Graph_theory/a">http://en.wikipedia.org/wiki/Graph_theory/a">http://en.wikipedia.org/wiki/Graph_theoryhttp://en.wikipedia.org/wiki/Graph_theory/a
James Devlin on November 15, 2008 12:33 PMMy favorite NP-Complete problem is bin-packing. Maybe shape separability.
Dan Lecocq on November 15, 2008 12:35 PMWhy do you make some many laymen sort of posts about how we should all be learning more about computer science (when many of probably have CS degrees and have known about this since sophomore year of undergrad days) but you think learning C is useless?
Just wondering.
Charles on November 15, 2008 12:44 PMTo Jon who is railing about more well rounded people in this industry: You realize this is a technical blog right? Sure there may be non-technical project managers reading this but its kind of pointless to have a laymen sort of discussion with a manager of a K-Mart about Approximation Algorithms. Why would you even do that? You're just showing your ignorance by perpetuating some stereotype about technical people going back to their caves.
Charles on November 15, 2008 12:47 PMGenetic algorithm. It has worked well for TSP, thus I've always kept a good GA library (with some timeout stoppers for example no improvement in solution during X seconds, or no exceeding X seconds of total computation ) in order to solve NP-Probs when they have arisen.
Jok on November 16, 2008 2:36 AMWhy can't I vote-up these answers? :p
Dean on November 16, 2008 2:41 AMWhen reading this post, it surprised me how it depends on the circumstances when you're first heard the term NP-complete. Jeff calls it a shorthand for incredibly hard, but I always remembered it as easy. How come?
At university, I wondered whether I should study computational linguistics and attended a first lecture about syntax theories to get a glance about what that subject is like. The problem is to syntactically parse a sentence in natural language using a computer. In that lecture, if a syntax theory is NP-complete, that meant good, quickly solvable in polynomial time. Not NP-complete meant bad, takes exponential time to solve. But the worst case (in that lecture some version of a Chomsky syntax theory) was plainly unimplementable.
My interest for computational linguistics originated in my enthusiasm for text adventures (today called interactive fiction) many years before (on a Commodore 128), so I'd call well written textadventures with bewitching graphics (Magnetic Scrolls) as my favorite NP-complete cheat.
NP = Not Possible [in linear time]
BTW, Jeff, I don't know if you would read my comment, but since your captcha is always orange, and I never see any spam in any of your blog, how did you manage that?
@Steve,
You asked:
Can someone solve this?
a=b
so, a^2 = a*b
so, a^2 - b^2 = (a*b) - b^2
factor: (a+b)(a-b) = b*(a-b)
cancel: (a+b) = b
so, 2b = b
so, 2 = 1
There are many variations to this type of puzzles. I knew or rather learned from 7th grade that all of them either involve (1) dividing by 0 or (2) Take a square root and ignore the fact the it's rather the absolute values that are equal.
Kevin Le on November 16, 2008 3:36 AM-----
NP = Not Possible [in linear time]
-----
Not quite... but in line with the blog post.
NP = Nondeterministic polynomial
it means that it can be solved with a polynomial order algorithm in a Non-deterministic Turing Machine. A non-deterministic Turing Machine is a Turing Machine which can take many paths of conditional execution at the same time.
Eric Londaits on November 16, 2008 4:09 AMMy favorite NP-problem and hack must be the Quake 3 engine's sqrt() function.
http://www.codemaestro.com/reviews/9
Martijn Laarman on November 16, 2008 4:13 AMJeff: Unfortunately, not all NP-complete problems have good approximations.
The very definition of NP-complete shows this to be false; that a problem is NP-complete means all problems in NP can be reduced to this problem. If you have an algorithm for one NP-complete problem, you have an algorithm for all of NP.
porges on November 16, 2008 4:21 AMWhile I and some of the other critics here have done a pretty good job covering where Jeff went wrong, I decided to give this a go myself: http://joeganley.com/2008/11/np-completeness-i.html ... I plan to write further installments in the coming weeks on attacking NP-hard problems: heuristics, approximation algorithms, exact algorithms, restricted problem inputs, and general optimization algorithms (like simulated annealing).
Joe Ganley on November 16, 2008 4:46 AMWe know exactly what NP-Complete means: it is defined as the set of decision problems that can be solved in polynomial time on a nondeterministic Turing machine.
P can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.
We know exactly how to show that a problem is NP-Complete: to show that with polynomial time on a deterministic Turing machine, we can convert solving that problem into solving all NP-complete problems. Reducing a problem is another word for encoding it, and it's NP-Complete if the encoding work is small.
bIf you wanted to, you could write a program to convert any np-complete problem to some program that would run in polynomial time on a non-deterministic Turing machine, and your program would run in polynomial time if you did it correctly./b
The definitive definition paper
http://www.cs.toronto.edu/~sacook/homepage/1971.pdf.gz
I was in a class where we did this, making the transition from 3-SAT to a nondeterministic Turing machine notation. It was boring.
John the Statistician on November 16, 2008 4:51 AMCan't you all see Jeff is just trying to provoke you? After all he's quoting a cartoon as evidence in his comment.
I think this is a good strategy...
1) pretend you really don't get the point
2) have a buch of foolproof explanations attached to your blog-post for free.
Well, have fun.
Alex on November 16, 2008 5:02 AM@Alex: just because Jeff has no regard for mathematical truth doesn't mean that it isn't worth our time if we do. (I don't mean this negatively, necessarily. I think it's a natural outcome of combining a practical, only-when-I-need it outlook with the strong opinions weakly held position. Just because it's bullshit in the Harry Frankfurt sense, doesn't mean it isn't a fine way to go about things.)
John the Statistician on November 16, 2008 5:10 AMI'll answer the original question:
- Simulated Annealing
- Great Deluge
- Genetic Algorithms
Writing the optimal blog post would have taken a very very long time.
Nice approximation, Jeff.
Poor old Jeff. He tries, he really does.
Well after the beating he's taking by various over nerds I feel I ought to make him feel better.
Ok here goes.
I had absolutely no idea what you were talking about, and even less about what you're detractors are talking about.
You're not the only guy who doesn't understand stuff Jeff
PixelGnome on November 16, 2008 5:31 AMI think what just happened here is called market segmentation.
Some part of Jeff's readers have a course in computability theory under their belt, so they are rightfully angry at the informal definition of a very formal entity.
The other part, whose lives were full without using the term NP-complete, may have gotten a glimpse of this interesting notion.
Kudos for this, Jeff.
Here's Dorit Hochbaum's book about approximations (not hacks) for NP-hard problems:
http://www.ieor.berkeley.edu/~hochbaum/html/book-aanp.html
(I guess this is more for the first crowd...)
Hey Jeff,
Cool cartoon.
No, I do not take what you read as gospel, anyone who takes a single opinion from the interweb, and embarks upon a course of action based upon that, deserves whatever they get.
I read this blog because I find it entertaining, and sometimes it prompts me to go and learn something new, or revisit something that I had long since forgotten.
I am not going to defend you as a mathematician or computer scientist, as that is not the point of this blog. Had you posted this in a scientific journal, then it may well be appropriate for others to take such vocal umbrage at your lack of academic rigour.
Having inherited a few systems from mathematicians and academics, and suffered the horrors of making them work in the real world, that is not a perspective that I seek unless I have to.
This is edutainment, has never pretended to be anything else, and there is nothing wrong with that.
Like I said, cool cartoon. Works for a code monkey like me.
seanb on November 16, 2008 6:23 AMCan someone solve this?
a=b
so, a^2 = a*b
so, a^2 - b^2 = (a*b) - b^2
factor: (a+b)(a-b) = b*(a-b)
cancel: (a+b) = b
so, 2b = b
so, 2 = 1
No Googling!
Steve on November 16, 2008 6:50 AMdivision by zero exception
Alex on November 16, 2008 7:05 AMUmm, you definitely CAN define that a problem is NP hard or complete. It's called a proof. If you can prove that a problem is NP*, you can thus prove to yourself (or others) that the actual solution is intractable. So you can stop trying to find one, and focus on
a.) redefining the problem
b.) using approximation algorithms
It's not about rigor. It's completely wrong. You are dumber as a result of having read it.
seeuo on November 16, 2008 8:32 AMIs it just me, or has this blog turned into ads for books lately?
Grom on November 16, 2008 9:26 AMTravelling SalesPerson is one of my favorite examples of why you should spend some time refining the requirements of you problem when you run into something that might be NP-Complete. Not only is the TSP problem easy to approximate, only the general case of TSP is NP-Complete. TSP when all of the points are co-planar (a pretty common case on the planet Earth) is *not* NP-Complete.
Sean Reilly on November 16, 2008 9:57 AMJeff Atwood: 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.
This is incorrect - the Cook-Levin theorem (http://en.wikipedia.org/wiki/Cook%27s_theorem) proves that the problem 3-SAT is NP-Complete. My understanding of the history is that Cook published in 1971; Levin's work was done around the same time, but not published until a bit later, and it didn't become so well known in the West, as Levin is Russian. For that reason, the result is often known as Cook's theorem.
Since that time, thousands of problems have been proved NP-complete, usually using a problem known to be NP-Complete, like 3-SAT, and a reduction. Garey and Johnson contains several hundred such problems, and many more are known today.
What is not yet known is how to prove that NP-Complete problem cannot be solved in polynomial time. If that could proved, it would solve the famous P vs NP problem.
(That aside, thanks for your blog, which I greatly enjoy.)
Michael Nielsen on November 16, 2008 9:57 AMI very seldom see much acknowledgement that there are *lots* of complexity classes far far higher than NP (and thus problems much much harder than NP-complete ones), and that in practice the limits of worst-case tractibility are substantially lower than NP: algorithms which run slower than O(n^2) are seldom tolerable in practice.
In many cases there's no such thing as an approximate solution: you can approximate a best path, but figuring out whether or not there is *any* path satisfying some set of conditions is all or nothing. In those cases, the best approach is to set aside the worst case and focus on realistic cases. There are plenty of very hard problems (NExpTime and higher) which can be solved in time close to O(n log n) on the kinds of data that tend to be encountered in practice.
If I were a manager and programmer came to me saying this problem is in such a high complexity class it would be impossible to solve! I'd encourage the programmer to identify patterns in the type of data we expect that could be exploited for optimization. A formal definition of this tractable fragment of the original problem may sometimes be difficult to codify, but that's beside the point if you can solve the problems you encounter. It's easy to phrase any easy problem as a subset of a much harder problem; the trick is to identify the truly necessary bits of the problem and see how hard that part is on its own.
The criticism I'd level at high-complexity research is that academics can dwell on the really hard problems (because they're interesting) and skip quickly over simplifications (because they're trivial and not worthy of study).
Rob Shearer on November 16, 2008 10:35 AMHaving scanned over the other comments, it seems that a lot of people are complaining about the article again. Well, I don’t. It might not be the most accurate description but it brings the point across (and I just like the analogy). Plus, some of the comments are sooo much worse. Consider the very first one: “… because … nearly any other NP problem can be reduced to [3-SAT].” This reveals a complete misundestanding of NP-completeness and the concept of reduction.
With that out of the way, I want to answer your question. I’m undecided between three very different cheats. The first uses cutting planes to literally “cut away” parts of the (mathematical formulation of the) problem to make it easier. I like it of its practical importance. Take TSP. Nowadays, this problem has very good solvers that use this approach (often combined with branch-and-bound to yield branch-and-cut), combined with raw computation power, to tackle even extremely large problem instances. For instance, CONCORDE has found the exact solution for the 24,978 cities of Sweden.
The second approach, Lagrangean relaxation just has to have a place in the list because of its elegant mathematical derivation. By applying a Lagrangean multiplier (that can be found easily) to one term of the problem, the overall runtime of the problem can be drastically decreased.
The last cheat is ant colony optimization. The underlying analogy is just fascinating. Also, implementing this solution is very easy and just plain fun. With the right sets of parameters, this heuristic often leads to very good results. Unfortunately, there’s no guarantee for good results which is simply unacceptable for many problems.
konrad on November 16, 2008 10:55 AMHey Now Jeff,
Those cartoons are really funny.
Coding Horror Fan,
Catto
I think we're missing the main definition in this post:
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.
So, we must define hardcore pornography first, and then discuss if it's or not NP-Complete, isn't it?
alberto on November 16, 2008 11:22 AMThese approximations to NP-Complete problem solutions, i'd be surprised if the quality of the approximation didn't degrade significantly with the input size - to the point perhaps where they're not useful anymore.
I would expect this but i don't remember seeing it confirmed anywhere. I mean, otherwise we'd have a probabilistic polynomial-time algorithm for solving NP-Complete problems (and i don't think we do because last i checked, 5 secs ago on wikipedia, the relationship between BPP and NP was another unsolved problem). In fact i think i remember seeing that likely BPP and P are equivalent (something about derandomization), so since probably P != NP, BPP != NP and we can't have a good approximating algorithm (for all input sizes).
Meaning, these approximating algorithms are no good for large input sizes, but please correct me if i'm completely wrong.
Bobby on November 16, 2008 11:26 AM-----
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.
-----
This is so wrong it hurts.
To add something constructive to the Jambalaya, I should note that not all high complexity - won't solve in a million-billion years for a large problem problems are NP-Complete...
... there are problems that are just as hard, or harder, and don't have the decency of being NP-Complete, but still require the use of approximations and heuristics.
Eric Londaits on November 16, 2008 11:56 AMIs NP-problems like hardcore pornography? I never thought there were a substitute for that, thanks for now I'll be solving Travelling Salesman problem instead... hope it will get me the same pleasure..
Jack on November 16, 2008 12:28 PMThat's fancy computer science jargon shorthand for incredibly time-consuming, or incredibly hard to solve quickly, or more specifically incredibly time-consuming to solve, and pretty quick to verify the solution
You got it backwards. For most NP-Hard problems, devising a solution is easy. It's verifying the solution is correct that is difficult.
His definition is sufficient (and sarcastically enjoyable) for those who are trying to solve these problems in the real world.
The ever wonderful real world argument tha plagues software development. It's not sufficient. I honestly don't really care what the software engineering defintion is, it's incorrect and misleading. The reduction componenet of the definition is crucial because it can help you devise approximations to solve the problem. After all, it's too hard doesn't always work.
Delmania on November 17, 2008 1:02 AMAs someone with an advanced degree in CS, I don't think his explanation was all that bad.
Compare it with Wikipedia's definition, which is effectively infinitely recursive:
a class of problems having two properties:
* Any given solution to the problem can be verified quickly (in polynomial time); the set of problems with this property is called NP.
* If the problem can be solved quickly (in polynomial time), then so can every problem in NP.
Not nearly as useful to the layman, IMHO. I do believe there's a better definition involving a combination of Turing machines and set theory, but if you don't already know about Turing machines that wouldn't be particularly useful to you either, without a twelve paragraph exposition on the subject.
T.E.D. on November 17, 2008 1:15 AMHow about having a new classification, for those us for whom mathematical proofs don't play such a large part in our working lives, so as not to offend our more erudite colleagues:
FK Hard - you'll know it when you see it
Sigh. So, to those who want to fight over the correct definition. What do you do for a living?
I would really like to know if anyone who is actual front line developer (not a researcher or comp sci teacher) has ever found the technical difference to be useful.
I have been in the field for quite a while now, and most everything you are taught in CS is absolutely useless.
In addition, I would like to know if any of you have been out of college for more than two years.
Prove me wrong. Really. I would like to know if there is such a case where proving how hard a problem is would actually be useful in a business environment. (Not a theoretical case, a real one, that actually happened).
Practicality on November 17, 2008 1:27 AMIs this blog NP Complete?
OG on November 17, 2008 1:55 AMPracticality --
Embedded system to automate paint designs on walls efficiently. I won't bore you with the finer details (and there were many), but it was trivially reproducible to a travelling salesman problem. As such, I was able to go through the existing body of work and determine which well-known algorithms had sufficiently low complexity to work given my constraints (which translate to constant-factors) before trying to program every bloody one of them in assembly and then watching to see if it moved right away. It was critical and saved countless hours. And I can only do it because we know with true rigour that the TSP is NP-complete.
Now I do mostly systems programming in C++ on desktop computers in performance-critical applications working for, let's keep this somewhat anonymous, one of the top-5 software development companies as ranked by revenue. NEXPTIME isn't an important term here, but a basic idea of complexity analysis that's a little more sophisticated than I know it when I see it is and has been absolutely necessary. More sophisticated and more not completely wrong.
You're right though, I'm not long out of school -- ~1.5 years. However, I didn't take CS, I took Engineering (not Software or Computer or Electrical Engineering), and while we briefly covered big-O notation analysis we didn't really deal with P=NP. I picked this up partly on my own time and partly on the job.
I don't mind if you don't know these facts, particularly if it isn't in the least bit relevant to what *you* do. But I do mind complete falsehoods being paraded around as facts. Even that wasn't so bad, but I'm aggravated to see people defending the error (including Jeff!? I sure hope he's just confused and asking for clarification instead of claiming it's not wrong). It's an error. We all make errors, even popular bloggers. That doesn't make it not an error.
Ens on November 17, 2008 1:57 AMAs an example, writing a non trivial web site that displays exactly the same in all major browser is NP-complete, and any semi experienced web developer have learned its way to the 3% from optimal solution.
jwickers on November 17, 2008 2:00 AM@Ens
Neat. Thank you for the informative story. Believe it or not, your real life explanation of how you solved that problem would fascinate me, but that's what I am looking for :).
However, I would argue that the fact you looked it up yourself would validate that we don't need to know this information ahead of time to enter the field.
Also, I would agree that, technically, Jeff made an error. He should say most of us can't define it (or don't care to), rather than nobody can.
However, I do think this a minor and picky error, when the intent of the post was to say that when you encounter such a problem, you need to find a workaround.
I think the harsh insults directed at Jeff for making a technical error of very few versus nobody are far worse than making the error itself.
Practicality on November 17, 2008 2:15 AMI came up with a generic solution for the TSP a couple of years ago. Here's a hint... fractals. And lagrange polynomials. I leave the rest as an exercise for the reader.
Peter Maxwell on November 17, 2008 3:14 AMMy favorite algorithm is the Ant Colony Optimization, actually a solution to the traveling sales man. It is in fact a brute force algorithm and still it's better than real brute force. It starts as pure brute force but already after several iterations some solutions will turn out as being so sub-optimal, that the algorithm will hardly consider them anymore and thus the algorithm finds a solution much faster than real brute force. Real brute force would try all solutions, even if a solution seems to be very suboptimal at first, it might turn out to be an optimal solution in the long run. This is however very unlikely when usang ACO. Solutions that look sub-optimal in the very beginning are usually sub-optimal. If some ants are already back home while others are still on the way, the route used by the other ones is definitely worse than the one of the ants already back home.
Mecki on November 17, 2008 4:06 AMJeff is actually right here, and the CS types are barking up the wrong tree. This discussion is about the _software engineering_ term NP-complete, not the mathematical term of the same name. As he says:
--
Have you ever heard a software engineer refer to a problem as NP-complete? That's fancy computer science jargon shorthand for incredibly hard:
--
Lots of other fields have similar confusion caused by a shared use of a word or phrase - for example, both religious studies and architecture use _postmodern_, for completely different things that some people tie themselves into knots trying to justify as essentially the same.
It might avoid future similar confusion if developers were to use the more mathematically correct term _superpolynomial_ when they want to say 'really hard, so we shouldn't do it' without sounding lazy. The only downside is other developers won't understand it they way they would the less mathematically correct term.
soru on November 17, 2008 4:08 AM@Practicality: I've been out of school for 14 years, and spent the first 10 of those years working on problems (many of them NP-hard) of optimizing the layout of computer chips. Making real software that is sold to and used by chip designers at semiconductor companies like Intel, AMD, nVidia, and the like. You doubtless own many pieces of electronics that were designed using software that I wrote. (I'm just making the point that I am neither a researcher nor an academic, but a working software engineer.) Being able to determine which of the problems I encounter is NP-hard is critical to doing this well. Often, trying to determine that a problem is NP-hard when it isn't provides the critical insight to solving it. Only a really sorry engineer writes a heuristic for a problem that can in fact be solved efficiently, just because he doesn't know the difference between NP-hard and I can't easily figure out how to solve this.
I don't know what kind of work you do, but I use much of what I learned in CS every day, and have done so in every job I've ever held.
Joe Ganley on November 17, 2008 5:01 AMIt seems like all the people defending Jeff here are also trying to defend themselves for not knowing a basic CS term.
I really, really hope that I don't have to do any significant amount of work with any of the people who are saying it's of no practical significance in the real world.
I've been out of college more than 2 years, and I use a very large proportion of the CS that I learned in my job. I'd leave the industry if I was just cranking out boilerplate code all day - and pretty much any time you get ahead of boilerplate there's usually something helpful from CS.
While you can look up stuff and pick it up if you go a) you'll pick it up faster if you have the basics of CS under your belt to start with and b) you'll be able to make better choices various data structures and algorithms throughout the less challenging work that improve your code.
There is no fight over the correct definition - there is one correct definition and Jeff wasn't really close. I think people might be complaining because they've mentally filed this blog in the 'reliable information' and they're begrudging the mental work to re-file it elsewhere.
My personal reason for adding my voice to the fray is that I think having a highly visible, incorrect and misleading piece of information out in the wild is really going to hurt those that are going to try to pick these things up on their own.
Dave on November 17, 2008 5:06 AMsometimes coming up with clever cheats can be more interesting than searching in vain for the perfect solution
Word.
Smart: understanding and recognising an NP-Complete problem.
Gets things done: uses a suitable approximation.
Paul D. Waite on November 17, 2008 5:11 AMUnfortunately, not all NP-complete problems have good approximations.
Err, wait a minute. I thought one of the characteristics that made a particular problem NP-Complete as opposed to NP-Hard was that all other NP-Hard problems could be reduced to it. Therefore, wouldn't it stand that if you have a good approximation for the one NP-Complete problem, you'd have a good approximation for them all?
I have to admit I fell into the trap of refering to the TSP as NP-Complete, but only because it's the one that we're always taught.
Jeff is actually right here, and the CS types are barking up the wrong tree. This discussion is about the _software engineering_ term NP-complete, not the mathematical term of the same name
No, Jeff is not right here. NP-Completeness is a shining example of where the theory and the practice meet. It defines the limitations on what can be done with a computer. It's more than knowing that a problem is hard, it's knowing why it's hard, and what you can do to work around it. The software engineering definition is incredibly misleading and simplistic, as it ignores the fundamental point that all NP-Hard problems can be reduced to an NP-Complete problem. That's very powerful, because that means that if you're trying to come up with a way to get a result from something you know to be NP-Hard, you can reduce it to an NP-Complete problem and approximate that.
Delmania on November 17, 2008 5:21 AMThe comments to this entry are closed.
Subscribe in a reader
Subscribe via email
|
|
Traffic Stats |