7
$\begingroup$

In Richard Karp's paper "Reducability among combinatorial problems" he lists 21 NP-Hard problems. Though I can somewhat understand the ideas and motivation behind the paper I am searching for some clarity.

From what I know and understand this paper showed the parallels between the various problems. Specifically that they are all abstractly the same problem. That given a solution (specifically a P-time solution?) to one of these problems you could solve all of them because they are all statements of a more abstract problem.

Is this a proper summary of the work he presents? Is there a more eloquent and proper yet short way to say it?

Karp's paper: http://www.cs.berkeley.edu/~luca/cs172/karp.pdf

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I think this is a duplicate of our reference question. $\endgroup$
    – Raphael ♦
    Feb 24, 2015 at 6:43
  • $\begingroup$ Disagree. This question is asking for the historical motivation and summary of contribution of a specific paper. None of the answers on the reference question even mention the paper ("Karp reductions" are mentioned once in the encyclopedic 60K character answer to that question.) @LukeMathieson's answer here would not be appropriate for the reference question. $\endgroup$
    – Wandering Logic
    Feb 24, 2015 at 13:17
  • $\begingroup$ @WanderingLogic I inferred "please explain the concept of NP-completeness in simple terms" as main query. Maybe I'm wrong. $\endgroup$
    – Raphael ♦
    Feb 24, 2015 at 13:57

3 Answers 3

Reset to default
8
$\begingroup$

The short way to say it is that these problems are $\mathcal{NP}$-complete.

Of course this only has meaning to those who understand what $\mathcal{NP}$-complete means.

Not only does this say these problems are all somehow equivalent (polynomial-time equivalent to be marginally more precise), but that you can use them to solve any problem in $\mathcal{NP}$, not just each other, with only a polynomial blow-up in the time cost. This immediately gives us that if any of them have a polynomial-time algorithm, then everything in $\mathcal{NP}$ does, and hence we would have $\mathcal{P} = \mathcal{NP}$ (summed up in Theorem 3 from the paper).

To see what Karp's paper in particular represents however, we have to pay attention to a touch of history (not all that usual for most computer scientists I know, but bear with me ;) ). This paper was published in 1972, it was only the year before that Cook proved that $\mathsf{Satisfiability}$ was $\mathcal{NP}$-complete , this was the first "natural" problem proven $\mathcal{NP}$-complete1, but Cook doesn't mention $\mathcal{NP}$, let alone $\mathcal{NP}$-completeness (and he used a weaker type of reduction than Karp, but that's another story). So what you see in Karp's paper is the first codification some of the ideas that have formed one of the central parts of complexity theory, not only does he get these ideas out into the literature, he also says "hey, there's a lot of problems that we're interested that are $\mathcal{NP}$-complete".

So in one go, he coherently defines $\mathcal{NP}$-completeness, shows what it means for solving problems efficiently2, and gives a bunch of (interesting) problems that are $\mathcal{NP}$-complete.

In some sense it is the founding document of complexity theory. It took a lot of ideas that were starting to gain currency, and put them together in a (relatively3) clear statement of how all this complexity stuff can work.

Footnotes

  1. The definition of $\mathcal{NP}$ almost immediately gives complete problems - anything along the lines of "Does this non-deterministic Turing Machine halt in a polynomial number of steps?" or similar, but these are not the most interesting problems in the world (to most people).
  2. Using Edmonds' idea of deterministic polynomial-time as a working definition of "efficient".
  3. Though the reductions are fairly cursor and opaque by modern standards. On the other hand, he crams 21 in there.
Improve this answer
$\endgroup$
3
  • $\begingroup$ Ok this brings the whole idea together for me, thank you. // Out of interest, seeing that all of these are related. As I mentioned in the OP, is there a specific abstract problem that represents NP problems? As Karp showed, they are all reducible to each other in P time. Is there some "meta problem", that all these problems reduce to; also that this meta problem is the simplest explanation of an NP problem? For example TSP adds the "frills" of a sales person and routes, etc. Is there something that shows the issues without the "frills"? (the frills represent the P-time translation to each pro) $\endgroup$
    – KDecker
    Feb 24, 2015 at 23:14
  • 1
    $\begingroup$ @BumSkeeter, yes an no, I don't think there's a problem that is particularly satisfying in this regard, though $\mathsf{Satisfiability}$ is very clean, just simple Boolean, propositional logic, but to really see why this is a useful characterisation, you have to dig into the structure of the Polynomial Hierarchy. Of course there's a version of the Halting Problem inherent in the definition of $\mathcal{NP}$ which is very abstract (Input: TM $M$ and the string $1^{n}$ with $n \in \mathbb{N}$. Question: Does $M$ accept on an empty tape in $n$ steps?). One of the problems with trying to find... $\endgroup$
    – Luke Mathieson
    Feb 24, 2015 at 23:37
  • 2
    $\begingroup$ @BumSkeeter ...such a problem is that $\mathcal{NP}$-complete is a rather rough class. You can get away with an awful lot in polynomial-time, so you can reduce quite different problems to each other. For example, despite being $\mathcal{NP}$-complete, $\mathsf{Vertex Cover}$ and $\mathsf{Satisfiability}$ have very practical, effective algorithms, whereas $k$-$\mathsf{Coloring}$ is rather intractable. All classic $\mathcal{NP}$-complete problems, but quite different when you look at them with a bit closer. $\endgroup$
    – Luke Mathieson
    Feb 24, 2015 at 23:42
4
$\begingroup$

To add some to the other already detailed answer: Cook's paper introduced the class of NP-complete problems but only gave a single "canonical" instance, SAT(isfiability). Karp showed in his paper in a "few strokes" that a wide variety of open problems that did not previously seem to be linked were in fact all NP-complete. So this later paper demonstrated somewhat dramatically it's more than merely an isolated or narrow theoretical curiosity; it's a basic classification in computer science, and hinted that many more (NP-complete problems) lay waiting to be identified, and that was exactly the case.

That view has only grown significantly in subsequent decades as NP-complete problems are found to be quite ubiquitous and cross virtually all scientific mathematical fields. There are now in the hundreds of NP-complete problems identified, possibly over a thousand (in a sense computer scientists have lost track somewhat, and at times it becomes difficult to discriminate "separate" problems from each other).

Nice modern surveys of this perspective can be found in e.g.:

Another related historical reference that came out in 1979 later and catalogued extended Karp's ideas to dozens of problems organized by category is:

Improve this answer
$\endgroup$
0
0
$\begingroup$

Here is more research about the problems themselves:

enter image description here

The gist of it is that the problems are indeed all NP-Complete, but their individual complexity varies a lot. While any NP-Complete problem can be reduced to any other, creating actual reductions is difficult. Satisfiability happens to be much easier to work with than most other NP-Complete problems.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.