Open and Closed Problems in NP-Completeness

DIKU Distinguished Lecture by David S. Johnson, Columbia University, hosted by EADS

The Theory of NP-Completeness today provides links between the many areas of computer science, together with important questions in mathematics, operations research, economics, and even the physical sciences. A resolution to its central question, whether P equals NP, will now win you a $1,000,000 Millenium Prize. A "yes" answer might yield a wide-ranging technological and scientific revolution, while a "no" answer will at least allow the Internet commerce industry to feel a bit more secure.

"In this talk I say a little about the history (and pre-history) of the theory, which was initiated in 1971 by Steven Cook and Leonid Levin, independently, and then broadly illustrated by Richard Karp in 1972. I survey some of the major NP-completeness and polynomial-time solvability results since then, as well as the many failed attempts at proving (or disproving) P = NP. I conclude with an exploration of the ways in which the theory has expanded from feasibility and optimization questions to ones about approximation, greatly assisted by the alternative characterization of NP in terms of "probabilistically checkable proofs" in the early 1990s, and list some of the key open questions remaining in this domain."

David S. Johnson

In 2010 the ACM Special Interest Group on Algorithms and Computation Theory presented its 2010 Knuth Prize to David S. Johnson of AT&T Labs for his contributions to theoretical and experimental analysis of algorithms. Johnson’s innovations helped lay the foundation for algorithms used to address optimization problems, which involve the process of finding the best solution from all feasible solutions. In addition, Johnson made many contributions to the early development of NP-completeness theory, which helps identify those problems that are hard to solve efficiently.

Johnson’s research in approximation techniques to solve computational problems set up the basic theoretical framework and approach for searching for an “almost” optimal solution. His work over the years has addressed the approximation of many problems including bin packing, which is an NP-hard problem that applies to filling up containers, loading trucks with weight capacity, and creating file backup in removable media. It also addresses TSP (the Traveling Salesman Problem), which can be useful in planning, logistics, and the manufacture of microchips, as well as DNA sequencing.

In addition to his theoretical analysis, Johnson has authored a set of highly influential papers on the experimental analysis of approximation algorithms. This research established equally rigorous standards for experimental algorithms, which focus on implementations as the standard of value and provide the key to the transfer of research results from paper to production code.

Johnson is an acknowledged expert on NP-completeness, a reference to the hardest search problems. His 1979 book, Computers and Intractability: A Guide to the Theory of NP-Completeness, which he coauthored with Michael Garey, remains the standard reference on the topic. Johnson has also written continuously on NP-completeness in his columns for the Journal of Algorithms and ACM Transactions on Algorithms.

An active leader in the theoretical computer science community, Johnson founded the ACM-SIAM (Society for Industrial and Applied Mathematics) Symposium on Discrete Algorithms (SODA) and the ongoing series of DIMACS (Center for Discrete Mathematics and Theoretical Computer Science) Implementation Challenges. He served on the ACM Council as Member-at-Large from 1996-2004, and chaired ACM SIGACT from 1987-1991. He was editor of the Journal of the Association for Computing Machinery (JACM) from 1983-1987, and ACM Transactions on Mathematical Software (TOMS) from 1991-2006. He has also served as associate editor of ACM Transactions on Algorithms (TALG) since its founding in 2004.