Colloquium

The question of P vs. NP is one of the central questions in computer science and mathematics. (It is one of the Clay Institute Millennium 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.