Time-Space Tradeoffs and Lower Bounds for Satisfiability

Sam Buss

(UCSD)

A series of results by several authors in recent years have given alternation-trading proofs that Satisfiability is not in the simultaneous time- and space-bounded class $\DTISP(n^c,n^\epsilon)$ for various values $c<2$ and $\epsilon<1$. In this talk, we characterize exactly what can be proved in the $\epsilon=0$ case with currently known methods, and prove the earlier conjecture of Ryan Williams that $c=2\cos(\pi/7)$ is optimal for this.

We also give a new a theoretical and computational analysis of alternation-trading proofs for $0<\epsilon<1$. This both gives new lower bounds on the computational complexity of Satisfiability, and establishes precise numeric limits on what lower bounds can be proved with currently known alternation-trading techniques.

This is joint work with Ryan Williams.
Tuesday 1st March 2011, 14:00
Robert Recorde Room
Department of Computer Science