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!
Ryan Williams, IBM Almaden Research Center, San Jose, USA
Josef Raviv Fellow at IBM since September 2009