Citation: Richard M. Karp, Raymond E. Miller, James W. Thatcher. Reducibility Among Combinatorial Problems. The Journal of Symbolic Logic, Vol. 40, No. 4 (Dec., 1975), pp.618-619. (PDF)

Abstract: A large class of computational problems involve the determination of properties of graphs, digraphs, integers, arrays of integers, finite families of finite sets, boolean formulas and elements of other countable domains. Through simple encodings from such domains into the set of words over a finite alphabet these problems can be converted into language recognition problems, and we can inquire into their computational complexity. It is reasonable to consider such a problem satisfactorily solved when an algorithm for its solution is found which terminates within a number of steps bounded by a polynomial in the length of the input. We show that a large number of classic unsolved problems of covering, matching, packing, routing, assignment and sequencing are equivalent, in the sense that either each of them possesses a polynomial-bounded algorithm or none of them does.

Discussion: This 1975 complexity theory paper showed that a diverse set of 21 classic intractable problems are NP-complete, highlighting the importance of NP-completeness and providing the first strong evidence that P ≠ NP.

To briefly review, a problem is said to be solvable in polynomial time if there is an algorithm that can produce a solution in a number of steps that is bounded by a polynomial of the input length in bits. The set of all problems solvable in polynomial time is called P. A problem is said to be verifiable in polynomial time if, given a problem instance and a candidate solution, there is a polynomial-time algorithm to determine whether or not the candidate is a correct solution. The set of all problems verifiable in polynomial time is called NP. The NP-complete problems are a particularly difficult-to-solve subset of problems in NP having the property that if any of them can be solved in polynomial time, then all problems in NP can be solved in polynomial time.

To understand the importance of this paper it is essential to ignore much of what we know about NP-completeness today and examine the context at the time: Cook, who introduced the concept of NP-completeness, had shown that NP-complete problems exist; this by itself was surprising, in that by solving a single problem efficiently, we could solve an entire class of problems efficiently, an attractive proposition. He also demonstrated a “natural” example of an NP-complete problem: the boolean satisfiability problem. Classical progress on this problem had been such that it was not unreasonable to suppose that a polynomial-time algorithm for this problem might yet be found if we just worked hard on the problem (see my prior post on the DPLL algorithm).

Karp’s paper dashed any hope of such a simple resolution. All of the 21 problems shown to be NP-complete in this paper were well-known, well-studied problems that had seen a barrage of algorithm development from researchers for many years; many of them hoped to find a polynomial-time solution to the problem, but failed to do so. Given the two possibilities, that either all of them had polynomial-time solutions, or none of them do, it seems more natural to conclude that the latter is the case; this is equivalent to the statement that P ≠ NP, which is now widely believed to be true, although it has not been proven (see P vs. NP problem).

Simultaneously, Karp’s paper also opened the floodgates for thousands of more problems that would be shown NP-complete in the following years; because problems are shown to be NP-complete by reducing known NP-complete problems to them, the more NP-complete problems are known, the easier it becomes. This paper critically aided in bootstrapping that process.

Moving on from impact to practicum, the methods of this paper were straightforward, even for the time; this was very much a case where what was proven mattered more than how. The algorithms, relevant complexity classes, and notions of completeness are defined in the conventional manner in terms of Turing machines, with remarks that the classes are robust against reasonable changes in the computing model and input encodings, and they review Cook’s results. They list some classical problems with nontrivial polynomial time solutions, such as 2SAT, minimum spanning tree, and shortest path.

Finally, they show their main result. To show a problem NP-complete, it suffices to show that is in NP (verifiable in polynomial time) and that an existing NP-complete problem can be reduced to it, in the sense that there is a polynomial-time algorithm that can take any instance of the existing NP-complete and translate it to an equivalent instance of the new problem with the same yes/no solution. Karp defines the 21 problems and includes a diagram (pg.96) showing which problems are reduced from which other problems in the proof. Compared to a typical modern homework assignment, Karp’s proof is very sparse: he omits as trivial showing that the problems are in NP, and the reductions are specified in only two or three lines each defining a reduction function; that the functions specify a correct reduction and are polynomial-time computable is considered self-evident. He also shows that a number of problems from automata theory are NP-hard; in fact, these problems turned out to be PSPACE-complete in later work.

Finally, he lists three problems whose NP-completeness was unknown at the time, and today they are considered very unlikely to be NP-complete: linear programming, primality testing, and graph isomorphism. In 1979, the ellipsoid method provided a polynomial-time solution for linear programming. In 2002, the AKS primality test solved primality testing in polynomial time; the related factoring problem is not believed to be NP-complete either, since that would imply NP=coNP. The graph isomorphism problem does not yet have a polynomial time solution, but in 1988 Schöning showed that if it is NP-complete, the polynomial time hierarchy collapses to the second level, which is also considered unlikely.

Returning to impact, Karp’s paper may have also had the unfortunate side effect of stymying research in some areas: researchers were no longer motivated to seek polynomial-time solutions to NP-complete problems, because under the assumption that P ≠ NP, such a search is fruitless. Although investing in research that is more likely to succeed is a good plan for the individual researcher, if it turns out that P = NP, the intuition to the contrary generated by Karp’s paper may delay and impede the eventual proof of this fact.

In some cases this change in research direction extended to not working on algorithms for these problems at all. But Karp’s 21 problems are still important practical problems that need efficient solutions, if not in general then at least in practice. A familiar result from computability theory is that the halting problem is unsolvable, but for most programs that arise in practice it’s trivial to tell whether they eventually terminate or not. Similarly, many NP-complete problems have effective practical solutions: the boolean satisfiability problem is “easy on average” and modern heuristic SAT solvers can handle typical inputs with millions of clauses; problems like the knapsack problem have a polynomial time approximation scheme that allows solutions very close to the optimum solution to be found quickly; and problems like the travelling salesman problem have been attacked with great effectiveness by virtually every new optimization method, as well as new computing paradigms such as DNA computing. These approaches gain credibility from the NP-completeness of their test problems, because they have a theoretical basis with which to fend off claims that they should instead have sought a solution with good worst-case behavior. Considering slow progress on the P vs. NP problem itself, practical approaches such as this are likely to dominate the study of NP-complete problems for the foreseeable future.

The author releases all rights to all content herein and grants this work into the public domain, with the exception of works owned by others such as abstracts, quotations, and WordPress theme content.