The most famous problem of theoretical computer science — known to mathematicians as P versus NP — will be the subject of a talk this week by Ronald Fagin, whose groundbreaking 1973 doctoral thesis at Berkeley proved what would become renowned as “Fagin’s theorem.” The Clay Mathematics Institute in 2000 identified P versus NP as one of its seven “Millennium Prize” problems, offering $1 million to whoever can solve it.
Fagin, now with the IBM Almaden Research Center, will describe the problem for a general scientific audience, and explore the sociological phenomenon of “community refereeing” on the Internet — a procedure that helped unravel questions about one recently attempted solution. The colloquium will include what Fagin describes as a “high level” discussion of the approach of that effort, and of issues that were raised during the community-refereeing process.
The talk, sponsored by Berkeley’s Group in Logic and the Methodology of Science, is scheduled for Friday, April 8, at 4:10 p.m. in 60 Evans Hall.