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