Colloquium Details
Open and Closed Problems in NP-Completeness
Speaker: David Johnson, Columbia University
Location: Warren Weaver Hall 1302
Date: November 7, 2014, 11:30 a.m.
Host: Richard Cole
Synopsis:
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.
Notes:
In-person attendance only available to those with active NYU ID cards.