Date: Thursday Nov. 6, 2003
Why is the "P vs. NP" question still open?
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.