Favorite Theorems: Combinatorial NP-Complete Problems

April Edition

If Cook made the P versus NP question interesting to logicians, Karp made the question important to everyone else.

Richard Karp, Reducibility Among Combinatorial Problems, Proceedings of a Symposium on the Complexity of Computer Computations, 1972.

All the general methods presently known for computing the chromatic number of a graph, deciding whether a graph has a Hamiltonian circuit, or solving a system of linear inequalities in which the variables are constrained to be 0 or 1, require a combinatorial search for which the worst case time requirement grows exponentially with the length of the input. In this paper we give theorems which strongly suggest, but do not imply, that these problems, as well as many others, will remain intractable perpetually.

Karp's paper used Cook's Theorem that satisfiability was NP-complete to prove 21 other problems NP-complete, including Clique, Integer Programming, Hamiltonian Cycle, Chromatic Number, Partition and Max Cut. Many of these problems arise from real-world optimization problems and Karp showed that if any of them have efficient algorithms then they all do. Researchers would later extend Karp's techniques to show hundreds if not thousands of natural problems are NP-complete.

Karp's paper named the classes P and NP and defined the notion of reduction (now often called Karp Reduction) where a language A reduces to a language B if there is a polynomial-time function f such that x∈A iff f(x)∈B. He defined a notion "polynomial complete" as the set of problems A in NP that every other NP-problem reduces to A, a notion we now call NP-complete. Karp also makes the argument that the definitions are robust to different reasonable encodings of the problem and different models of Turing machines.

Karp also alludes to the polynomial-time hierarchy.

If P=NP then NP is closed under complementation and polynomial-bounded existential quantification. Hence it is also closed under polynomial-bounded universal quantification. It follows that a polynomial-bounded analogue of Kleene's Arithmetic Hierarchy becomes trivial if P=NP.

Karp lists three NP problems whose classification was open at the time.

• LINEAR INEQUALITIES: Basically Linear Programming, shown to be in P in 1979 by the recently departed Khachiyan.
• NONPRIMES: Shown to be in P in 2002 by Agrawal, Kayal and Saxena.
• GRAPH ISOMORPHISM: Not known to be in P but if GI is NP-complete then the polynomial-time hierarchy collapses which was shown in 1987 by combining results of Goldreich-Micali-Wigderson, Goldwasser-Sipser and Boppana-Håstad-Zachos.