Speaker: Sam Buss, University of California, San Diego
Title: Limits on Alternation-Trading Proofs for Time-Space Lower Bounds
This talk discusses alternation trading based proofs that the NP-complete problem Satisfiability (SAT) is not in the time and space bounded class DTISP(n^c,n^ε), for various values c<2 and ε<1. We characterize exactly what can be proved in the ε=0 case with currently known methods, and prove the conjecture of Williams that c=2cos(π/7) is optimal for this. We also discuss bounds for ε>0. These results give upper bounds on the best lower bounds for Satisfiability that can be obtained with alternation trading proofs. This is joint work with Ryan Williams.