4:00 pm Thursday, September 8, 2011

Moshe Vardi (Rice University - CS)

The question of P vs. NP is one of the central questions in computer science and mathematics. (It is one of the Clay Institute Millenial Problems whose solution would yield an award of $1,000,000.) In August 2010, an HP researcher claimed to have solved the problem, using tools from mathematical logic and statistical physics, including a theorem proved by the speaker in 1982. The claim generated a huge buzz in computer science, with coverage also in the New York Times. This talk will explain what the P-vs-NP problem is, what tools were employed in the claimed proof, and what the status of the claim is.