The History and Status of the P versus NP Question
Michael Sipser
Video Download | Streaming Video
The History and Status of the P versus NP Question
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.
| 
