(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.

Robert Recorde Room

Department of Computer Science