Title: P versus NP: Approaches, Rebuttals, and Does It Matter?

Speaker: Neil Immerman, UMass Amherst

Abstract:

NP contains all those problems that we could efficiently solve if "guessing were free", i.e., all those problems whose solutions we could recognize as correct if they were given to us in an appropriate format and context.  We've known since 1971 that a large class of important combinatorial problems including boolean satisfiablity (SAT) are NP complete, i.e, hardest problems in NP.  If any of these had a solution in P, then so would all other problems in NP.

How hard is SAT, or any other NP-complete problem?  It is well believed that P is not equal to NP and that SAT requires exponential time on some hard instances.  However, SAT solvers are now in practical use as general problem solvers, currently working even on instances with a million variables. 

I will explain some of these issues, laying out what we do know, what we do not know, and what we hope to understand once the P versus NP question, together with many similar but less famous open questions, are finally resolved.