SAT Solving and Complexity Theory 

My goals for this talk are:

  • To reacquaint you with complexity theory, and explain the "relativization barrier" to lower bounds
  • Tell you about the state of the art regarding P versus NP 
  • Tell you how SAT solving could help prove new theorems in complexity theory!

Some of the slides from the "complexity theory refresher" are adapted from a longer talk on P versus NP given by myself, Ken Clarkson, and Ron Fagin.
Video for that talk can be found by following this link.

Ryan Williams, IBM Almaden Research Center, San Jose, USA

Josef Raviv Fellow at IBM since September 2009

  • No labels