FAQ  ||  donate  ||  DVDs

 The History and Status of the P versus NP Question

Speaker: Michael Sipser
Date: May 8, 2001
Real Video: 383 MB

Talk Introduction

In a remarkable 1956 letter, Kurt Godel asked John Von-Neumann whether certain computational problems could be solved without resorting to brute force search. In so doing, he foreshadowed the P versus NP question, one of the great unanswered questions of contemporary mathematics and theoretical computer science.

In my lecture, I will discuss the history of this question, including Godel's letter. I will also explain some of the efforts made in recent years toward its resolution.

About the speaker

Michael Sipser is Professor of Applied Mathematics in the Theory of Computation Group at MIT. He is also the author of Introduction to the Theory of Computation, the textbook used in the Theory of Computation course at ADU.

License

The colloquium series videos are licensed slightly differently than our normal classes. These are covered by the Creative Commons Attribution-NoDerivs license which allows free copying but does not allow for the creation of derivative works.