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?
I can see both sides of the argument here. Jeff has at least brought to light the idea of NP-completeness to many people who otherwise wouldn't have even heard of the concept. Ok, there are inaccuracies in his post but hopefully those that are interested will follow it up. However, that is where the problem lies. Many people are not that great at thinking for themselves and don't check out the facts that they have been given are actually correct. I see this every day. They take a snippet from a blog and think it's gospel. The problem seems therefore to be not Jeff's post per say, but those that don't expand and complete their knowledge of the subject. Anyway, Jeff's post inspired me to write a post on NP-completeness in a little more depth over at own blog (http://www.equivalence.co.uk/), hopefully this may be of use to Jeff and others.
Gregg on November 17, 2008 6:00 AMJeff, I think you went too far this time.
This is not the We have no idea about IT, but we want to look knowledgable blog. This is programming and human factors blog.
Couldn't you write the post without all those childish mistakes?
NP-complete is not another name for very hard. No.
Imagine, there are NP and NP-complete classes of problems - and both of them are very hard. Know the difference between them? If not, please do not write about computer science.
Jakub Anderwald on November 17, 2008 6:34 AMIn cryptography, getting the right answer is all that's important, and getting an approximation is next to useless. Take an example of creating a parallel cryptographic hash function (like md5 or sha-1) where you hash small chunks, but then add all the outputs as large integers, and hash this sum one more time. This is essentially the subset sum problem. There are many ways (through dynamic programming and such) to find approximate solutions, but you haven't compromised the cryptography unless you find an exact match. Getting it within 2-3% of the correct solution only reduces your search space from 2^80, in the case of sha-1, down to 2^74 or so, which is still an intractable problem.
Matt Ball on November 17, 2008 6:37 AMJesus people, he's not writing a university text-book here, it's a blog! Lay off a bit, or at the very minimum be more constructive with your criticism.
I don't think introducing someone to a new, interesting subject is a bad thing in any way. And maybe even a little mis-information (not that it is even there!) will weed out the ones not willing to research the topic on their own.
I also find it amusing that people will actually spend the time to read the post and then berate the author. If you don't like what he has to say, the solution is simple, DON'T READ IT! It's not an NP-Complete problem!
Kory on November 17, 2008 6:40 AMI think saying a CS degree has no practical value is a big stretch. But, then again, having a CS degree doesn't necessarily make you a good programmer either!
dismountSoapbox();
Kory on November 17, 2008 6:46 AMInteresting to see you bring up the bin-packing problem. I used variants of the known implementations to create an output image that tried to have the least possible area for a given image set.
Theres source code on my site with it in 12/12/07, I was smitten with finding variants of different sizes and outputs. Really fun stuff.
Jake Heidt on November 17, 2008 7:08 AMgreat post jeff. but the alt text on the xkcd img should really be fixed to read as on the actual cartoon page.
Sean on November 17, 2008 7:35 AM'as it ignores the fundamental point that all NP-Hard problems can be reduced to an NP-Complete problem'
Actually, not true: many 'Np-hard' (s/w eng definition) are, in strict mathematical terms, exponential, or just polynomial with impractical coefficients. Outside military cryptography, there is rarely a pragmatic difference between 'would take a CPU-week' and 'if you turned the Sun into computronium, would still take longer than the heat death of the universe'.
Either is too long to wait for a web page to refresh.
To a zoologist it's Bos Taurus, to a farmer it's a cow. The more precise terms are sometimes useful, but if you want to talk to a farmer, you don't have to use their language, but you'd better understand it.
soru on November 17, 2008 8:10 AMBy the amount of scrolling I had to get to the bottom of the page, can I safely assume that writing a blog post about NP-Complete that doesn't freak people out is NP-Complete?
Neil C. Obremski on November 17, 2008 8:48 AMIt's not cheating it's engineering. That's the diff betwixt science and engineering - otherwise we'd never get anything done.
iFubesi on November 17, 2008 9:33 AMRemove money and no salesmen are needed.
Silvercode on November 17, 2008 9:42 AMI'm beginning to think that pagination on Stack Overflow is an NP-complete problem, because it's still broken after all this time!
See a href=http://stackoverflow.com/questions/63241/what-is-the-strangest-programming-language-you-have-usedhttp://stackoverflow.com/questions/63241/what-is-the-strangest-programming-language-you-have-used/a">http://stackoverflow.com/questions/63241/what-is-the-strangest-programming-language-you-have-used/a">http://stackoverflow.com/questions/63241/what-is-the-strangest-programming-language-you-have-usedhttp://stackoverflow.com/questions/63241/what-is-the-strangest-programming-language-you-have-used/a and notice the two page fours. And yes, I have logged this on UserVoice: a href=http://stackoverflow.uservoice.com/pages/general/suggestions/65993http://stackoverflow.uservoice.com/pages/general/suggestions/65993/a">http://stackoverflow.uservoice.com/pages/general/suggestions/65993/a">http://stackoverflow.uservoice.com/pages/general/suggestions/65993http://stackoverflow.uservoice.com/pages/general/suggestions/65993/a
John Topley on November 17, 2008 9:49 AMApparently we can't *prove* anything is NP-complete
What I think you mean to say is: We can't *prove* NP-complete problems are hard.
NP-complete is not a synonym for difficult. Some people think it is, and you may hear it used that way, but that does not mean you should encourage it. We already have a perfectly cromulent word for difficult, and that word is difficult.
Michael G on November 17, 2008 10:41 AMI prefer genetic algorithms for NP-hard problems, that are transformable into a genetic algorithm (i.e. TSP).
MTZ on November 17, 2008 12:10 PMNot that I think some of the criticisms of this article aren't warranted, but to those of you who keep screaming about the formal definition of NP:
While Jeff's definition is certainly flawed in some respects, citing the formal definition of NP would be next to useless in the context of this blog. I challenge you to explain the practical implications of NP's formal definition to a lay-programmer in a way that you think is more correct than simply saying known algorithms for finding optimal solutions to NP problems have extremely high computational complexity.
I mean, saying here that NP is about quick verification of solutions and reducibility is the same as telling a layperson that e=mc^2 means energy equals mass times speed of light squared. No *practical* insight about the matter at hand is given by either definition without a lot of heavily mathematical and scientific pipelaying.
People usually appreciate having things explained to them in a way that doesn't make them feel stupid. I make such explanations all the time in my work. However, when I describe things to people using oversimplified abstractions, I make it a point to tell them that it is not *strictly correct* to think of it this way, and that the *truth* of the matter is much more complicated. But most of the time they are satisifed with, and can make much practical use of the simpler version plus caveat.
I don't think most of the serious commenters that are being identified as defending Jeff are defending his factual errors here as much as they are recoiling to the somewhat hostile and excessive pedantry being displayed. Hard and exact science is very important and (to me) fascinating. But it is not useful to shove *unnessecarily* large chunks of background theory down the throats of people who just want to get their work done, when some slighly innacurate but much simpler abstraction will almost always suffice for them.
Also, I disagree that your average software developer can't be expected to spot NP problems. In practice they are fairly easily spotted because almost ALL of them encountered in the wild are more or less isomorphic to some other known NP problem, like the Knapsack or TSP. Any good developer should be familiar with the relatively short list of infamous NP problems, and *should* be able to tell if the problem at his feet is just a variation on one of those.
Kyle S on November 17, 2008 12:21 PMNP-complete?
That'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
Oh please.
His definition is sufficient (and sarcastically enjoyable) for those who are trying to solve these problems in the real world.
The differences are irrelevant to dealing with them in the real world. They are really hard... too hard to solve in a reasonable amount of time.
That's all I need to know. For the rest, who cares?
Some people take these things too seriously. For the intended audience of this blog (read: developers, not computer scientists), this is an excellent definition.
Practicality on November 17, 2008 12:54 PMNP-complete problems are like hardcore pornography.
Jeff, I really think you need to get out more.
please don't fix the Conservapedia articles.
Well, except if *I* fix them, they'll be correct, no?
I've redacted the offensive sentence from the post, with explanation.
In all honesty, despite reading all the above comments and the wikipedia entries, I still don't quite understand the definition of NP-complete other than as we'll know it when lots of experts have seen it, tried, and failed.
There has to be a simpler definition out there somewhere. I talked to Joel Spolsky about this and he had a pretty good analogy that might work; I urged him to write a blog post about it.
Jeff Atwood on November 18, 2008 3:28 AMReminds me of this:
http://xkcd.com/386/
Jeff -
NP-complete is actually pretty simple, so I bet whatever sources you have been reading have just over complicated it.
'NP' is a class of problems - that is a set of problems that all share a particular property. Here, it's the property that they can all be solved in polynomial time by a Turing machine (or equivalent computer) that can - every time there's a choice point in the algorithm to solve it - magically guess the right decision to make.
So rather than have your Turing machine deterministically make the same decision at every choice point, our new machine somehow knows which is the right way to go.
That's what the NP stands for - 'non-deterministic polynomial'.
Imagine you're trying to solve the Travelling Salesman problem by brute force. Enumeration of all those graphs takes at least O(2!) time. However, our non-deterministic Turing machine magically guesses which is the right way through the search space, and can construct the circuit in polynomial time - by choosing the right edge (again, magically) at every choice point.
Now, the class of problems that can be solved in deterministic polynomial time is called P, and P is a subset of NP since every problem in P can also be solved by our non-deterministic Turing machine in polynomial time. What we don't know is if there is a deterministic polynomial time solution to all the problems in NP - if there was, then P=NP and bingo, you've won a million dollars.
To help us find out whether P=NP, computer scientists have discovered a kind of problem that is the *hardest problem in NP*. By hardest, we mean that any algorithm to solve the hardest problem will take as least as long to run as any other algorithm to solve any other problem in NP.
We call these problems 'NP-complete'. If we could find an efficient deterministic polynomial time algorithm to solve an NP-complete problem, we'd have shown that *every* problem in NP has an efficient solution, because remember by definition NP-complete problems are the hardest in NP.
(Sidenote: we show that a problem is 'harder' than another problem by showing that the easier problem can be reduced in polynomial time to an instance of the harder one. Then a solution to the easier one is found by reducing it to the harder problem and then solving the harder one, so at worst we can solve in the time it takes to solve the harder one. If you think about this carefully, you'll see this is exactly what we probably want 'harder' to mean.)
So that's all NP-complete problems are: the hardest problems that can be solved by a non-deterministic Turing machine in polynomial time. We don't know if a deterministic polynomial time solution to them exists - it may do, but I doubt it - but that doesn't change the fact that we can recognise them, prove them to be NP-complete, and formally identify them much more easily than we can hardcore porn :)
Henry on November 18, 2008 3:48 AMWell, that just begs the question - why the blog post in the first place? And why recommend a book that you haven't read and/or didn't understand? Not cheap shots here, I actually want to understand why you took that credibility risk with the people who know this stuff - which it turns out is a lot of programmers.
In all honesty, despite reading all the above comments and the wikipedia entries, I still don't quite understand the definition of NP-complete other than as we'll know it when lots of experts have seen it, tried, and failed.
Have you really read all of the above comments? Not just scanned over them but read them? You only know if a problem is NP-complete if the experts have seen it, tried, and proved that it's NP-complete. There's a precise definition and a set of criteria to demonstrate that something is NP-complete.
I'll have a crack at some explanations, I don't know how much help they'll be. I'm sure the book you linked to probably explains it better.
A Turing machine is a simple model of a computer. In its usual form its only output is to accept or reject and input, so instead of asking it what a + b is, you normally ask it if a + b = c - ie it solves decision problems.
A problem is in P (Polynomial time) if for all instances of a problem with size n (n = 100 if we have 100 objects to sort, for instance) the Turing machine takes a number of steps to come to a decision that is a polynomial in n - eg there's an uppper bound of 2 * n^5 + 4 *n + 5.
A lot of the time when we talk about the size we're talking about the number of bits - adding n-bit numbers is in P - O(n) - and so is ultiplying n-bit n-bit numbers - O(n^2) the simple way, although FFT methods do better.
This is where I back up for a second and talk about non-determinism. A regular expression is just a non-deterministic finite automaton or state machine. It has a state, and the next state is determined by the current state and the next piece of the input which is read.
Say we're scanning a bit string rather than a character string, and we're after strings that have a 1 as their tenth last bit. Using a regular state machine we're going to need about 2^10 states to handle this.
This is where we add non-determinism. We allow the machine to go to several different states based on the current state and the next piece of the input. Once we've read a 1 we're in a state with two paths - one leads back to the state we're in, and one leads to a string of ten states which all transition to each other on all inputs and end with an accepting state.
Rather than having the machine encode 2^n states we have the machine split into 2^n in different multiverses and we take a big OR of the results. The machine took n guesses that the current piece of input was the tenth last, and we were able to save some space describing the machine.
As a bonus you can easily implement a NFA engine with only a polynomial size increase in space / time for the processing over the deterministic equivalent, so they're both in P but I digress.
So we're processing the input of a Turing machine. Now we add non-determinism, so at every step the machine can split - so we have 2^n virtual-multiverse machines, if any of them say yes to the current decision problem then the answer is a yes. If the running time for each machine is bound above by a polynomial in n, we have a problem in NP.
That's why there's a polynomial size check (or certificate) of all NP problems - it's just an encoding of the n guess that were made to get to the accepting state. You can take the original non-deterministic turing machine and at each place where you would normally guess the certificate will tell you which path to take and guide you to the accepting state. It's like factoring the product of two large primes is hard but it's easy to check if you have one of them already via the mod operation.
The NP-complete problems are assumed to be the hardest of the NP problems. It all starts with SAT3 - just take it as a given for now that SAT3 is the first in the list of NP-complete problems.
Take a candidate for a second NP-complete problem. Using a polynomial number of copies (A) of this candidate problem and a polynomial sized amount of Turing machine glue code (B) try to show that you can solve SAT3 (or something else on the list). If you can, the candidate problem is NP-complete and you can add it the list.
So if solving NP problems takes exponential time, we have A * an exponential in n + B, and it takes a really long time to solve SAT3 and every problem between your problem and SAT3.
But if one of them can be done in polynomial time, we have A * a polynomial in n + B, and it takes polynomial time to solve SAT3 and every problem between your problem and SAT3.
You may have spotted that so far this means solving SAT3 in polynomial time doesn't do much for you. NPC is defined as the problems that are in NP and reduce to all other problems in NPC, and so for SAT3 to keep its crown you also build the tree in the other direction.
It becomes a crazy tangled web but it's clear that if you can solve one of the problems in polynomial time you can solve all of them in polynomial time just by stepping through the web from the P-time problem towards the problem you're after.
Dave on November 18, 2008 4:43 AMDave has it almost completely right above, except for a couple of details. The NP-complete problems aren't *assumed* to be the hardest problems in NP - they are proven to be, and the proof involves SAT instead of SAT3 (SAT3 is just SAT restricted to no more than 3 literals per clause).
This is what Cook's Theorem is all about, and it's why NP-completeness isn't as recursive as it looks. What Cook did was to show that given *any* decision problem in NP, we could take a description of the non-deterministic Turing machine that solves it, and produce in polynomial time an equivalent SAT problem that had a solution if and only if the NTM returned true along one of the paths in its original computation. So if we had a hypothetical polynomial-time algorithm to solve SAT, we could use it to solve every decision problem in NP in polynomial time - just take the description of the NTM that solves the original problem, produce the equivalent SAT problem, and turn our hypothetical SAT solver loose on that.
That's what showed that there was such a thing as NP-completeness in the first place, and showed that SAT was one such problem. All the other NP-complete problems have been shown to be NP-complete by showing that If we could solve problem X in polynomial time, then we could solve this other problem in polynomial time ... and therefore, we could solve SAT in polynomial time.
Terminology note: a decision problem is one with a boolean true/false result. E.g., does the following instance of the TSP have a solution with cost = B? Technically, NP (and therefore all the NP-complete problems) consists only of decision problems (by definition). The optimization problems that we are usually really interested in solving can be NP-hard, rather than NP-complete. A problem is NP-hard if a polynomial-time solution to it would imply a polynomial-time solution to an NP-complete problem. Thus What is the lowest-cost solution to the following instance of the TSP? is NP-hard, not NP-complete, but it should be pretty obvious that if we could solve it in polynomial time, we could also answer the related decision problem, which is NP-complete.
Dave W. on November 18, 2008 5:18 AMI think what Jeff means is that nobody can define what makes a particular problem belong to NP, but not P.
That is what I was trying to say. Poorly, obviously. I have updated the post.
I still say the definition of NP-complete is awfully.. *conveniently* .. recursive, as T.E.D. mentioned.
I also agree with this particular sentence in the Wikipedia (http://en.wikipedia.org/wiki/NP-hard) article: The NP-family naming system is confusing.
And how.
Jeff Atwood on November 18, 2008 5:35 AMI actually want to understand why you took that credibility risk with the people who know this stuff - which it turns out is a lot of programmers
I wrote about it for the same reason I write about anything, I'm trying to understand it. Sometimes you're successful, other times not so much. Life is a credibility risk; what are you gonna do? Not say anything until you're guaranteed to be perfectly right every time?
It becomes a crazy tangled web
Well, that part is clear.
Jeff Atwood on November 18, 2008 5:38 AM@T.E.D.:
The definition on Wikipedia is not recursive. I think the confusion may arise because NP and NP-Complete mean different things, and the definition of NP-Complete depends on the definition of NP.
A problem is *NP* if (roughly speaking) it's quick to check whether a proposed solution is correct. Note that this includes both easy and hard problems.
This definition of NP is not recursive. You can decide whether a problem is NP independent of other problems.
A problem is *NP-Complete* if it's both *NP* and if finding an easy algorithm to solve it would automatically give you an easy algorithm to all *NP* problems.
This definition of NP-Complete depends on the definition of NP, but it does not depend on itself.
Weeble on November 18, 2008 5:53 AMAnother reason it sounds recursive is that generally the way you prove a problem is NP-Complete is by showing that it's NP and then reducing another NP-Complete problem to it. So how do you prove that anything is NP-Complete in the first place? The answer is that this is only the easy way. The hard way is to prove that *every* problem in NP can be reduced to your problem. That's what the Cook-Levin theorem did for the SAT problem. Once you know *one* NP-Complete problem, it becomes easier to prove other problems are NP-Complete.
http://en.wikipedia.org/wiki/Cook–Levin_theorem
A problem is NP-complete if it is both [quick to check whether a proposed solution is correct] and finding an [efficient] algorithm to solve it would automatically give you an [efficent] algorithm to solve *all* [quick to check whether a proposed solution is correct] problems.
Isn't this.. er.. still.. partically recursive? We know it because solving one would solve all the others, which in turn solves the others, which in turn solves the others.. ad infinitum?
I have to say I find this topic *incredibly* confusing, even after reading all the above comments (many of which were quite helpful, thank you) and the relevant wikipedia articles.
Jeff Atwood on November 18, 2008 6:19 AMIsn't this.. er.. still.. partically recursive?
The definition involves infinite stuff (the set of all NP problems), but it is not recursive. The definition of NP stands alone, and the definition of NP-Complete depends only on the definition of NP.
The presence of infinite stuff isn't as big a deal as you'd think. You can prove that adding together any two odd numbers will give you an even number, even though there are an infinite number of odd numbers. I don't really understand the Cook-Levin theorem myself, but I'm happy to know that it shows that all of the infinite possible problems (including all the ones nobody has thought of yet) in NP can be converted to an instance of the SAT problem. That might seem surprising, but it's not all that different to proving something about all the infinite possible odd numbers. Then, with that in hand, you can go on to show that other stuff is NP-Complete, because if you can convert SAT to your problem, you know you can convert *any* problem in NP to SAT and then convert it to your problem.
Weeble on November 18, 2008 6:51 AM@Jeff
You've mentioned the explorative nature of your posts before and it just slipped my mind - sorry about that.
The blog post does read like you're telling people about something that you're pretty familiar with, which might be why the people familiar with NP / NPC are exploding on here.
For instance, I read the expert programmer line like you were in the pool of people who understood NP / NPC and were asking the other folk to jump in and test the water. Could just be me though.
I guess it's not about credibility, it's about being able to tell when you're expounding and when you're exploring. And I guess that's really a problem occurring in the space between you and readers - lots of stuff is missing when you're communicating digitally. Maybe throw in a hint next time to make it clear to those of us that are struggling to tell the two apart? :)
Good luck with the exploration :)
@Dave W - you're spot on.
Although I didn't meant that it _is_ assumed, I was just asking Jeff to trust me on it since it was already an overlong post :) It took enough restraint to avoid mentioning the different kinds of reductions.
Of course, now that you've mentioned it I'm kicking myself for not just saying you can emulate a NTM with a carefully configured instance of SAT.
Ok, not enough time to read all the comments that don't have the answer to the question, what's your favorite cheat? Mine: refactoring a hard problem such that I can avoid the part I want to avoid as much as possible. I imagine that there is a CS term for it, but I majored in English :) Clearly a lot of the commenters are smart--probably smarter and certainly more educated (in this field, anyway) than I; how does the flamage help anyone get things done?
That One Guy on November 18, 2008 7:34 AM@Henry: great explanation. Rather than repeating the self-referential jargon that other explanations used, you did a pretty good job of demonstrating what the concepts mean. If you could have avoided the terms 'Turing machine' and 'polynomial', it might have been better, but I (and presumably most) knew those anyway.
travis on November 18, 2008 9:53 AMIm sorry Jeff but your update is still somewhat wrong. You should abandon the thought NP-complete == hard-problem . It should be more like NP-comple = we think it's a hard problem.
I'll try to give an understandable and maybe partly informal definition of NP-complete below, bear with me (or ignore it, if you think it's not interesting).
NP-completeness is defined by two criteria:
1. The problem is in NP (aka the problem can be solved in polynomial time by a non-deterministic Turing machine. (Before I get flamed for mentioning Turing Machines: Regarding some previous posts by Jeff I think he knows what I'm talking about.)
Note this is trivially true for all problems in P (those which can be solved in polynomial time by a deterministic Turing machine). So P is a part of NP.
2. The problem L is one of the hardest problems in NP.
Let's say we have some magic box, which accepts the input for our problem L and gives us the correct output, taking only a fixed amount of time, independent of the input. Now to prove, that our problem L is the hardest, we have to show that we can solve all other problems in NP in polynomial time using our magic box (This is known as Reduction).
We do this by giving an algorithm, which transforms the input for other problems into input for our problem. Now showing something for ALL problems sounds difficult, but it can be done. (If you want to know how look up the Cook-Levin Theorem).
If we have one problem L', which is known to be the hardest it is enough to show that our problem L is equally hard. This means we only have to give an algorithm which solves L in polynomial time using a magic box which solves L'.
So, the Cook-Levin Theorem shows that we can transform every problem in NP into SAT. Going on from there we show that we can transform SAT into other problems, like Traveling Salesman, Bin Packing, etc. take your pick.
We think that we can't solve this problems in polynomial time on a non-deterministic Turing Machine (or on your average computer), but we can't proof that and if someone would come up with a way to solve one of these problems in polynomial time, we could solve all of them in polynomial time (we could just apply the algorithms, that we defined when we proved their NP-completeness).
However, even if someone comes up with such a solution (which is highly unlikely) the definition of NP-complete I gave above still applies to all of the problems, so they remain NP-complete. We only revise the deduction NP = difficult.
H on November 18, 2008 10:00 AMWow. Jeff Atwood, master troll!
I think I'm going to add Jeff's explanation of NP-complete to Conservapedia. http://www.conservapedia.com/Public-key_encryption
It's a pretty good imitation of a pop science explanation of CS terms, but with glaring errors that stand out to anyone with an undergrad CS education. (Nobody really knows what NP-completeness means... Problems are only NP-complete because we can't prove they aren't.)
Maybe Jeff can explain one-way hash functions next. (A one-way hash function is a way of implementing a read-only hash table, similar to Ada's 'const final' attributes.) Or branch prediction. (Branch prediction is the ability of a programming language to conditionalize certain instructions on flags in the hardware's ISR register.) Or garbage collection. (Languages such as Java are only considered garbage-collected because we can't prove they aren't.)
Anonymous Cowherd on November 18, 2008 10:54 AM(BTW, please don't fix the Conservapedia articles. The errors are intentional parody.)
Anonymous Cowherd on November 18, 2008 10:55 AMOkay, Jeff; I admit I haven't read all of these posts. But I'm going to try and clear up some of your confusion without using too many words. I aimed for 200, but I'm afraid I ended up needing 300:
We need to separate algorithms and problems. We write algorithms to solve problems, and they scale in a certain way. Although this is a simplification, let's label an algorithm with a 'P' if the scaling is good enough, and 'NP' if it isn't.
It's helpful to know things about the problems we're trying to solve, rather than the algorithms we use to solve them. So we'll say that all the problems which have a well-scaling algorithm are in P. And the ones which have a poor-scaling algorithm are in NP.
That means that lots of simple problems are in NP too, because we can write bad algorithms to solve easy problems. It would be good to know which problems in NP are the really tricky ones, but we don't just want to say it's the ones we haven't found a good algorithm for. After all, I could come up with a problem (call it X) that I think needs a super-amazing algorithm. I tell the world that the best algorithm I could come up with to solve X scales badly, and so I think that X is a really tough problem. But tomorrow, maybe somebody cleverer than me invents an algorithm which solves X and is in P. So this isn't a very good definition of hard problems.
All the same, there are lots of problems in NP that nobody knows a good algorithm for. So if I could _prove_ that X is a certain sort of problem: one where a good algorithm to solve X could _also_ be used, in some roundabout way, to give a good algorithm for _every_ other problem in NP. Well now people might be a bit more convinced that X is a genuinely tricky problem. And in this case we call X NP-Complete.
Tom on November 19, 2008 4:03 AMporges and Delmania: no, the existence of reductions from any NP-complete problem to any other doesn't mean that if one has good approximations then they all do. It can happen that there's a polynomial-time reduction from problem A to problem B but that it doesn't give you a good approximation for problem A even if problem B has one. (Crudely: suppose you've got something that turns solutions to B into solutions to A, but that turns almost-solutions with error x to B into almost-solutions with error rapidly_growing_function(x) to A. Then approximate solutions don't turn into approximate solutions even though exact solutions turn into exact solutions.)
It would be nice if people didn't use NP to mean hard, just like it would be nice if people didn't use exponential to mean big, but it probably isn't going to happen any time soon.
g on November 19, 2008 5:05 AMHi Jeff,
Please let me try a real simple explanation of the difference between P and NP... I hope I'm not repeating anyone, I haven't read all the posts. I won't bother repeating definitions I already saw above, just explain the difference (and why it isn't a recursive definition)
For a problem, M:
M is in P if, and only if, there exists an algorithm that solves M in polynomial time. In all cases, that means we know the algorithm and prove it's polynomial.
M is NOT in P if we have proven, absolutely proven, that there is NO algorithm for it that runs in polynomial time. This is, of course, much harder to prove, since you can't do with with an example - you have to prove it for all possible algorithms.
That would seem to cover all problems, but for quite a few problems, the answer is 'we don't know'. That's because there's no known polynomial algorithm for them, but also, there's no proof that there one doesn't exist.
This annoys computer scientists to no end.
In studying these problems which are unknown, it turns out that for a lot of them, you can devise a simple algorithm to tests a given solution, but not one to find a solution. The formal definition for them, given above in a lot of posts, is NP problems. Due to its definition, NP problems also include all P problems.
To complete things, it also turns out that quite a few of those NP problems are NP-HARD, which means that if you solve them in polynomial time, you can also solve all the rest in polynomial time.
A problem that is both NP-HARD and in NP is called NP complete.
So there you have it, a non-recursive and hopefully simple explanation.
Or
Or on November 19, 2008 5:20 AMI have never commented before and most probably will not again. There are two serious problems with the post, one of which has been fixed partly. But the second one hasn't.
1. Nobody can define what makes a problem NP-complete, exactly ....
It has an exact and precise definition, as pointed before. In your redaction you link to a poll about P != NP amongst computer scientists. How can this imply there is a confusion regarding the definition of NPC? Please take down the link as it is very misleading.
2. Your recommendation of Garey-Johnson - this book has a timeless quality. Have you read the book? Clearly you haven't. Otherwise you wouldn't be confused by the definition of NPC. It is obvious, you are strongly recommending a book you haven't read at all. This completely destroys you credibility as an author. You must preface the recommendation with the text - Disclaimer: I HAVE NOT READ THIS BOOK.
Since, you have claimed in your comments to still be confused by the definition of NPC, I will try and explain it in my own words, because it is quite simple.
Let U = set of problems.
Let P = set of problems that can be solved in polytime wrt size of the input
Let NP = set of problems whose solution can be verified in polytime wrt size of the input
Obviously P = NP = U
For example sorting an array of numbers
1. belongs to U
2. belongs to P, we can do this in nlogn
3. belongs to NP, given a array, we can check if it is sorted in polytime. In other words, Given an unsorted array, we sort it using a black box routine and verify if it is sorted in polytime. Let us say we do not know of any algo to sort numbers in polytime. This does not prevent the problem for belonging in NP. The problem may or may not belong to P. We don't know.
Another example, determine if a number is Prime
Before 2002
1. Belongs to U
2. Dont know if it belongs to P. No algo known
3. Dont know if it belongs to NP (I think). Simply stating that a number is prime, isn't enough, we need a proof of the fact, that can be verified in polytime. For a sorted array, it is simply the array laid out in sorted fashion.
After 2002 AKS polytime primality test, we KNOW that it belongs to P and hence NP.
Another example, does a graph have a Hamiltonian cycle (Google this).
1. Belongs to U
2. Don't know if it belongs to P
3. Belongs to NP. Given a cycle in the graph, we can verify if it covers all vertices of the graph.
Cooks theorem showed that if the 3-SAT problem, which belongs to NP also belongs to P, then ALL OF NP BELONGS TO P i.e. P == NP. Note that he did not prove that 3-SAT is in P. Just that if it were then, P == NP. Now many CS scientists are busy trying to prove that this implies a contradiction, i.e. P != NP, with noone succeeding so far. That's where the cartoon comes from.
Now we get to the definition of NPC - NP Complete.
After Cooks paper, Richard Karp proved that 21 problems that belong to NP are atleast as hard as 3-SAT, including the Hamiltonian cycle problem.
at least as hard means
1. Suppose you have a polytime solution for the Hamiltonian cycle. Then you can easily (in polytime) transform the 3-SAT problem into a Hamiltonian cycle problem. In other words, if you solve the Hamiltonian problem in polytime, you would have solved the 3-SAT problem in polytime as well. Like, if you can multiply complex numbers, you can also multiply real numbers.
Hence a polytime solution for Hamiltonian = polytime solution for 3-SAT = P == NP
Now, NP-Complete problems are those problems in NP that are at least as hard as 3-SAT, i.e. if even one of these problems were to belong to P, it would imply that all of P == NP. Starting with Karp's 21 problems, thousands of such problems are now known.
However note that the definition of NPC depends on convertibility of 3-SAT to it, and no-where on P == NP. A problem is NPC if the 3-SAT problem can be transformed into it in polytime.
Lastly
P = NP = NPC U
Please scratch the previous post, I meant
NPC lt;= NP lt; U
P lt;= NP lt; U
CSGradnowSoftEng on November 19, 2008 5:57 AMNice summary here:
a href=http://www.reddit.com/r/programming/comments/7ed4s/joel_on_software_calls_self_out/c06frjthttp://www.reddit.com/r/programming/comments/7ed4s/joel_on_software_calls_self_out/c06frjt/a">http://www.reddit.com/r/programming/comments/7ed4s/joel_on_software_calls_self_out/c06frjt/a">http://www.reddit.com/r/programming/comments/7ed4s/joel_on_software_calls_self_out/c06frjthttp://www.reddit.com/r/programming/comments/7ed4s/joel_on_software_calls_self_out/c06frjt/a
none on November 19, 2008 6:21 AMI don't know what's all the deal with NP, personally I found P-Space to be a much more interesting complexity class. Specially all that refer to the inclusion of the polynomial hierarchy into P-Space and the co-NP classes.
schizoid on November 19, 2008 7:29 AMI just wanted to say thanks to both Jeff and all the folks who commented who know more about this subject than I do. I appreciate that Jeff brought the subject to my attention because as an amateur software developer this is a topic way out of my league. Furthermore, the follow-up comments that corrected Jeff's writing were very enlightening and given me a deeper appreciation for the topic and piqued my curiosity. Good read!
Gareth Conner on November 19, 2008 7:36 AMThe only thing good about this post was the xkcd strip and it was not even yours.
however, coding horror will still remain in my google reader subscription.
i just hope jeff learned something from this fiasco.
K on November 19, 2008 8:32 AMI stopped reading the blog a while a go.
Hmm. The mystery of the non-reading reader. Another np-complete problem, I think. :)
Jeff Atwood on November 19, 2008 9:10 AMWell, I for one am sorry to hear that you redacted, NP-complete problems are like hardcore pornography. What an analogy! And it really got me wondering about simulated annealing ;-)
Kramii on November 19, 2008 9:19 AMJeff: The reason that NP completeness is not a matter of we'll know it when we see it is that there's a precise definition for NP completeness, and it's possible to formally prove that something is NP complete. What isn't known is if the class of problems known as NP is equivalent to the class of problems known as P. That means, we don't know if the existence of a polynomial time check of a result of a computation implies that there is an algorithm for solving the problem in polynomial time. We still can tell if something is in NP (just find an algorithm for verifying a solution, and prove that it runs in polynomial time). And NP-complete is just a subset of NP, the subset consisting of those problems that if you solved them in polynomial time, it means you could solve any other NP-complete problem in polynomial time. So, there is a precise definition of what's NP-complete, and you can prove if something is NP-complete. All we don't know is whether this implies that the problem can be solved in polynomial time, or if it implies that the problem cannot be solved in polynomial time.
Sorry, I haven't read every comment in the thread to tell if I'm being redundant; I just wanted to make sure it's clear that NP-completeness is well understood, and you can prove plenty of things about it, we just don't know whether or not there's a way to find polynomial time solutions to those problems.
Brian on November 19, 2008 10:49 AMI think this has actually turned out to be a very constructive post. Aside from all the offense and anger of course.
Practicality on November 19, 2008 11:21 AMBut now I have to read the book to get the rest of the story. Ahhh! Now I see the point! ;)
Practicality on November 19, 2008 11:41 AMMy favorite NP-complete problem is picking which clothes I'm going to wear on any given day.
PBEAN on November 19, 2008 12:22 PMI stopped reading the blog a while a go. Joel explains my reasoning nicely in his latest post:
This is not the way to move science forward. On Sunday Dave Winer [partially] defined great blogging as people talking about things they know about, not just expressing opinions about things they are not experts in (nothing wrong with that, of course). Can we get some more of that, please? Thanks.
Please check the approach from Chris Voudouris and Edward Tsang on GLS(Guided Local Search). My group is developing an optimization for this kind of problem for a well known governmental institution.But it can give you guys a good start.;-)
Andre.A on November 20, 2008 3:52 AMMark,
I have read this exact paper and no it does not solve the TSP problem optimally. It only provides an approximation. There is no known kind of hardware that can solve this problem in polytime, not even quantum computers.
hellfeuer,
There is a mistake in your description. You need to reduce B to A to prove NP-completeness of A (given that B is NP Complete), and not the other way around.
CSGradnowSoftEng on November 20, 2008 4:35 AMJeff Ouch -
I still don't quite understand the definition of NP-complete other than as we'll know it when lots of experts have seen it, tried, and failed.
An expert failing to solve a problem does not make a problem NPC. Anyone, expert or otherwise, providing a polytime reduction of a known NPC problem like 3-SAT or Hamiltonian cycle to the said problem makes the problem NP-Complete.
CSGradnowSoftEng on November 20, 2008 4:56 AMThe traveling salesman problem was solved back in the 80's by using a neural net. It's still slow but it could be solved in minutes instead of years. It is all a matter of using the correct hardware instead of software.
Many problems have much faster and even better answers if fuzzy logic is used instead of strictly formula based programming. Formula based programing is NOT a silver bullet for all problems. What happened to programming being about logic? Too much CS and not enough common sense.
@Jeff
A mistake in a blog post is no big deal ordinarily. But here
1) The mistake is fundamental. When the entire post is about complexity theory, I think you should at least understand the basics before you write about it, even if you are only trying to explain it to laymen as some have suggested (btw I am not a computer scientist)
2) You recommend a book you have not read.
If people are still confused about the recursive nature of the whole thing, here's how you prove a problem is NP complete:
You start with any one problem that is NP complete. This first one is the hardest, but this was done a long time ago (Cook-Levin theorem). They proved (independently) that SAT is NP-complete.
Now, given a problem you try to reduce it to a problem that you already know to be NP-complete. Here, we say problem A reduces to problem B if, given a solution to B, I can find a solution to A quickly (polynomial time).
Oh and if you cannot reduce it, then you cannot conclude anything (unless you PROVE that it cannot be reduced which is totally different) I don't know where you got the tried and failed idea.
So this is recursive only to the extent that in order to prove 'A' NP-Complete you usually use a B that is already known to be NP-Complete. Usually is the keyword here. You need not rely on a known problem, and Cook Levin did not. However, once ANY one problem is known to be NP-complete, we can recurse for the rest, which is much easier than proving from scratch.
Hope this helps.
hellfeuer on November 20, 2008 6:07 AMhttp://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.1391
Mark on November 20, 2008 6:18 AM@Mark
Cook has a paper on the science-fiction like results if P = NP. If it does turn out that way then I think everyone will know in the same way that people know that E = MC^2.
I don't think people are going to bluff their way to a decision about P ?= NP without understanding the reasons that it's difficult.
Not enough CS or common sense.
none on November 20, 2008 6:30 AMYour recommendation of Garey-Johnson - this book has a timeless quality
I meant that it was published in 1979, and the concepts behind it are still relevant and useful. Like, say, Peopleware. Compare to: Learn Visual Basic 5.0 in 24 Hours, or Microsoft WPF for Dummies. My reading list is full of books with this quality.
It is obvious, you are strongly recommending a book you haven't read at all.
Here's what I said: I'll recommend a book Anthony Scian recommended to me. Anthony's email to me indicated the book was a classic, I liked the topic (NP-completeness), and my initial research was intriguing -- if obviously incomplete. I don't have a problem with books being recommended in this friend of a friend fashion and I stated as such in the post.
Jeff Atwood on November 21, 2008 4:15 AMCook has a paper on the science-fiction like results if P = NP
One of the consequences is very startling. Given the mathematical proof of a statement we can read it and check it for correctness in reasonable time. i.e. What is difficult is actually finding the proof which can be incredibly hard. Finding the proof of a mathematical theorem is in NP by definition. Now if we were to prove that P == NP, then it could possibly put all mathematicians out of business. This means that given a provable mathematical statement, a machine can find a proof for it in polynomial time. If the order of the polynomial isnt too high, it would mean that Maths would end up like Chess, with mathematicians being unable to match machines in theorem proving. This possibility is either startling or very obvious, because human beings themselves are arguably nothing more than Turing Machines.
CSGradnowSoftEng on November 21, 2008 5:45 AMJeff is such a dumb bitch when it comes to anything like real CS, but what do you expect from someone too stupid to learn C?
@reader
I stopped reading the blog a while a go. Joel explains ...
It's quite curious: how could you know of this post if you stopped reading the blog?!?
Jeff,
The recursive definition bottoms out at 3SAT:
SAT was the first known NP-complete problem, as proved by Stephen Cook in 1971 (see Cook's theorem for the proof).
http://en.wikipedia.org/wiki/3-SAT#3-satisfiability.
Steve Steiner on November 21, 2008 10:04 AMFinding the proof of a mathematical theorem is in NP by definition
This is only the case for theorems that have reasonably short proofs (polynomial in the length of the theorem).
Your point about the startling consequences of P=NP is still good despite this nitpick: even an algorithm that could efficiently find proofs for theorems as long as they were at most 100 pages long, would still completely revolutionize mathematics.
Gareth Rees on November 22, 2008 2:35 AMhttp://www.experts-exchange.com/Q_20908880.html
After solving this problem, I gave a presentation of it to a local Comp Sci Department. One of the attendees had read a paper on the solving of such NP-hard problems with clever data representation. It was news to me.
Aikimark on November 24, 2008 3:39 AMSee www.timescube.com
stranger on November 24, 2008 9:51 AMCooks paper isn't just about proofs either - he talks about how you'd be able to do some pretty interesting things with music, art, etc...
D on November 24, 2008 12:08 PMWow Jeff, based on some of the incredibly scathing comments on this blog post, I've come to the conclusion that there are a lot dicks who read your blog ... Granted, there were some people who had the good sense to provide constructive criticism, but some of these folks need to chill out and realize that a blog is just a blog, not a CS textbook ...
-Ash
Ash on November 25, 2008 11:05 AMTo all of the PHds ripping into Jeff, you need to understand that the following is what your average corporate programmer got from this article:
mwop mwop bibble dingdo efi hookle wimby NP COMPLETE runky dfew oogle bing INCREDIBLY HARD toodle joply dfe CAN BE SOLVED ACCEPTABLY USING A CHEAT ioph fi zingzizzy jolbick GOOD BOOK: COMPUTERS AND INTRACTABILIY qopple redmind yobless imbo lunk.
Then they (we) get back to that finishing that Web based ASP.NET registration form.
Whether you like it or not, most readers could not give a #^$#* about your verifiably correct proofs, they are working programmers who are just trying to make a living.
@AJ
You should probably start to question your assumption that most readers of coding horror don't know or don't care about that NP Complete means - otherwise there wouldn't have been as many comments calling Jeff on talking about something he didn't really no about.
I can imagine that might change shortly - the blog post and Jeffs handling of the explosion on here seem to indicate the target audience may in fact be those doing Web based ASP.NET registration forms - and at least some of the people responding in these comments have probably already moved on.
And it's not like NP is something you need a Phd to learn about - it is / should be a standard part of a programmers education - whether at a learning institute or through self education. If I was a gardener and did gardening all day eventually I'd want to know things about the plants. Otherwise I'd just be a guy that digs holes and calls himself a gardener.
Pretty funny that Aikimark posts a link to experts-exchange.com
I wonder if his question appears on stackoverflow?
glenn jackman on November 28, 2008 9:24 AMWOW! So a lot of people read this, I wonder if Jeff writes the way he does (which I like a lot) just to piss off the people who's only job is to correct the Internet.
To you guys, the protectors of knowledge on the Internet I have to say, great job here.
You're next mission Wikipedia... good luck.
AnnMex on December 3, 2008 10:59 AMNP-Complete http://xkcd.com/287/
Dennis on December 6, 2008 10:40 AMhtml
bAb
/html
comments tl;dr
I don't know if this has been mentioned yet but there are problems harder than NP-complete.
mr. fappy on December 10, 2008 9:40 AMAnswering the original question, my favourite NP-complete cheats are Metaheuristics: evolutionary algorithms, simulated annealing, particle swarm optimization, ant colony optimization, estimation of distribution algorithms... what poetic names :-)
Those algorithms have the particularity to be stochastics, and they can't even guarantee that you will have an approximation of the optimum. But they do work for hard problems, and they sometimes are the only solution you can use...
nojhan on December 15, 2008 2:47 AMNow you know why this is The World's Most Dangerous Programming Blog
;)
Is it warmer in the country or in the summer?
Answer the result.
No-Prob Compleet on January 21, 2009 2:27 AMIf NP-completeness generates some much traffic, I look forward to the post about Undecidable Problems.
Undecided on January 21, 2009 11:36 AMAfter solving this problem, I gave a presentation of it to a local Comp Sci Department. One of the attendees had read a paper on the solving of such NP-hard problems with clever data representation. It was news to me.
http://proektbaza.ru/
For your next trick I strongly recommend trying to explain the Halting Problem. That should provide no end of 'interesting' feedback.
Oh yes, I apologise for having a PhD in CS, but I suppose we all have our crosses to bear!
Rik on April 18, 2009 5:06 AMYou should probably start to question your assumption that most readers of coding horror don't know or don't care about that NP Complete means - otherwise there wouldn't have been as many comments calling Jeff on talking about something he didn't really no about.
http://basetour.ru
Oftentimes, I'll find myself trying to find the solution to some random problem (or even a whole family), only to get stumped; monte carlo algorithims have often times bailed me out; being able to trade time and accuracy with a single variable can be very handy, especially since many problems rapidy approach specific values as the sample size increases. Thank god for logarithms.
Ghost2 on May 15, 2009 10:01 AMWow, many of the commentors here could easily be award-winning douchebags...
No wonder people hate nerds with such a passion. Many of you lack anything even similar to tact or social grace. It makes me feel better that, for all your arrogance, you'd die in the wild with the rest of the sheeple if it came down to it...
Learn to balance yourselves, people. Otherwise you'll turn out like M.
Jacob on May 15, 2009 12:55 PMJacob: Pot, meet kettle.
Joe Chung on June 1, 2009 11:34 AMMorons. If you blaim the blog of being bad, then I challenge you to write a better explanation we can scrutinize.
M,
explain NP completeness here, write a few words and see if you can do it better. If you can not, then stop being a prick. This is just a blog, nothing serious. People wont die if there are some inaccurieces. I dont complain if you use bad english or misspell words.
I, for one, rather enjoy Jeff's comments about computing. I work as a project manager for a small software company whose customers are not technical by any stretch of the imagination. Being able to communicate computer science ideas to the lay person, and make it enjoyable and understandable is not a simple task. Sometimes you have to dumb it down and stretch some ideas to make it work. So go bleach your brain, crawl back into your cave, and read your IEEE spec documents. Damn, can't we have more well rounded people in this industry???
Jon on February 6, 2010 11:13 PM@Charles: Ok, so the cave comment was knee-jerk and stupid, I admit it. My only point was that the industry _needs_ technical people who can communicate to and work with non-techies. This to me is a skill that is hard to find among your run of the mill software engineer.
By the way, I have a degree in C.S. and worked as an engineer for 6 years prior to my current position, so I am not ignorant to computer science principles. You're just showing your ignorance by perpetuating some stereotype that all project managers are non-technical :)
Jon on February 6, 2010 11:13 PMPlease 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. It's quite common that people misunderstand the the details of complexity theory, overestimate their grasp of the topic, and spread their misconceptions. I'm surprised that even some of my most talented developer friends have this trait. And I certainly had it all wrong until grad school.
People who DO
..oops hit enter too soon.
People who DO know the topic CAN explain it in accessible ways, and DO NOT utter blatant falsities. Some examples of this is:
This problem, like many others, is NP-complete. Sigh, everything good in life is NP-complete (meaning, many important problems that we need and would love to solve are, unfortunately, NP-complete. It is ABSOLUTELY TRUE that NP-completeness crops up more than we'd like... and sometimes in unexpected places)
P ?= NP issue is analogous to why ordinary people can't compose like Mozart, but can still appreciate his work for the genius that it is. (listening and appreciating music is like being a verifier, you can check that a solution to a hard problem is correct, but you can't produce the solutions yourself. An ordinary person could brute force it by continuously composing until something came out that was magnificient... but then that could take a very very long time).
THESE comments are constructive... AND correct.
Jason on February 6, 2010 11:13 PMIt's actually NP-hard, not NP-complete. There's a distinct and important difference between the two. It doesn't look like you bothered to even read the Wikipedia article you linked.
Jason on February 6, 2010 11:13 PMWaitaminute...! A reference to a traveling salesman, and not one crack about a farmer's daughter?
Incredible.
Improbable.
Infinitely improbable.
The comments to this entry are closed.
Subscribe in a reader
Subscribe via email
|
|
Traffic Stats |