ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-031 | 8th March 2011 20:26

Limits on Alternation-Trading Proofs for Time-Space Lower Bounds

RSS-Feed




TR11-031
Authors: Sam Buss, Ryan Williams
Publication: 11th March 2011 08:08
Downloads: 953
Keywords: 


Abstract:

This paper characterizes alternation trading based proofs that satisfiability is not in the time and space bounded class $\DTISP(n^c, n^\epsilon)$, for various values $c<2$ and $\epsilon<1$. We characterize exactly what can be proved in the $\epsilon=0$ case with currently known methods, and prove the conjecture of Williams that $c=2\cos(\pi/7)$ is optimal for this. For time-space tradeoffs and lower bounds on satisfiability, we give a theoretical and computational analysis of the alternation trading proofs for $0<\epsilon<1$.



ISSN 1433-8092 | Imprint