Hey 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?
These 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.
Is 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âŚ
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
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.
As 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.
How 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).
Is this blog NP Complete?
Practicality â
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.
As 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.
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.
I 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.
My 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.
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. 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.
@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.
It 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.
sometimes 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.
Unfortunately, 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.
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.