Beyond Computation: The P versus NP Question

Speaker:

Michael Sipser (Massachusetts Institute of Technology)

Additional panelists:

Richard Karp, moderator (UC Berkeley), Ron Fagin (IBM Almaden), Russell Impagliazzo (UC San Diego), Sandy Irani (UC Irvine), Christos Papadimitriou (UC Berkeley), Omer Reingold (Microsoft Research), and Ryan Williams (Stanford University).

What are the theoretical limitations of computer power?

In a remarkable 1956 letter, the great logician Kurt Gödel first raised this question when he asked the famous mathematician and computer pioneer John von Neumann whether certain computational problems could be solved without resorting to a brute force search through many possibilities. In so doing, he foreshadowed the P versus NP question, one of the major unanswered questions of contemporary mathematics and theoretical computer science. This question asks whether every problem whose solution can be easily verified by a computer can also be easily solved by a computer. An answer to this question would reveal the potential for computers to solve puzzles, crack codes, prove theorems, and optimize many practical tasks.

The event begins with a talk on the P vs NP question, by Professor Michael Sipser of MIT. This will be followed by a panel discussion, in which a group of distinguished computer science theorists will join Sipser to illuminate the current status of the question and our prospects for resolving it. Light refreshments will be served before the lecture, at 5 p.m.

About Michael Sipser:

Dr. Michael Sipser is a theoretical computer scientist, member of the Computer Science and Artificial Intelligence Laboratory (CSAIL), and Professor of Mathematics at MIT. He received a PhD in Engineering from the University of California, Berkeley in 1980 under the supervision of Manuel Blum in the EECS Department, and a BA in Mathematics from Cornell University in 1974.

He has been on the faculty of MIT since 1980, where he was Chairman of Applied Mathematics from 1998 to 2000. He has been Head of the Mathematics Department since July 2004 and is also currently the interim Dean of Science. He was a research staff member at IBM Research in 1980, spent the 1985-86 academic year on the faculty of the EECS department at Berkeley and was a Lady Davis Fellow at Hebrew University in 1988. His research areas are in algorithms and complexity theory, specifically efficient error correcting codes, interactive proof systems, randomness, quantum computation, and establishing the inherent computational difficulty of problems. He is the author of the widely used textbook, Introduction to the Theory of Computation (Cengage, 2005).

His distinctions include the MIT Graduate Student Council Teaching Award, 1984, 1989 & 1991, and the MIT School of Science Student Advising Award, 2003. He is a Fellow of the American Academy of Arts and Sciences.