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.
|