Date: Thursday Nov. 6, 2003

Time: 1:30pm

Place: ASB9705

Speaker:

Valentine Kabanets

Title:

Why is the "P vs. NP" question still open?

Abstract:

The question whether SAT is in P has been open for over 30 years. After many
fruitless attacks on this question, computer scientists have come with a few
explanations why the currently known techniques are not powerful enough. In
this talk, I'll try present these explanations in an informal/non-technical
way. In particular, I'll show why the diagonalization technique (which was used
by Goedel and Turing to show their famous results) does not suffice to resolve
the "P vs. NP" question. I'll also talk about "natural proofs"
of Razborov and Rudich, and why such proofs are not powerful enough to show
hardness of SAT.