Loading Events
  • This event has passed.

Beyond Computation: The P versus NP question, May 9

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.