Event Detail

P and NP are “complexity classes”. The problem of whether they are the same is renowned in computer science and mathematics, and a solution yields a Clay Millennium Prize of one million dollars, mathematical immortality, and deep insight into efficient computation. In August of 2010 there was a lot of excitement over the announcement of a possible solution: a claimed mathematical proof that P and NP are different, using ideas from mathematical logic and statistical physics. We will describe the P vs. NP problem at a high level for a general scientific audience. What is this problem? How is it important? We will also discuss the fascinating sociological phenomenon of mathematical refereeing in “internet time”. Finally, we will discuss the idea of the attempted proof, and issues that were raised during the “internet refereeing” process.

The biweekly LOGIC TEA will be held in the Alfred Tarski Room (727 Evans Hall) immediately following the Colloquium (with support from the Graduate Assembly).