Talk Introduction
In a remarkable 1956 letter, Kurt Godel asked John VonNeumann 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 AttributionNoDerivs license which allows free copying but does not allow for the creation of derivative works.
