Samuel R. Buss and Ryan Williams.
"Limits on Alternation-Trading Proofs for Time-Space Lower Bounds"
Computational Complexity 24, 3 (2015) 533-600.
Earlier version in Proc. IEEE 27th Annual Conference on Computational Complexity (CCC), pp. 181-191, 2012.
Both the CCC'12 conference version and the full preprint version are available here
Download revised full manuscript:
original submission date August 8, 2011.
Download CCC'12 conference version: PDF.
See also: a short related survey paper.
Abstract: This paper characterizes alternation trading based proofs that satisfiability is not in the time and space bounded class DTISP(nc,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. For time-space tradeoffs and lower bounds on satisfiability, we give a theoretical and computational analysis of the alternation trading proofs for 0<ε<1.Download: Full Excel spreadsheet table of data for Figure 3 from the paper reporting simulation runtimes for searching for DTISP alternation trading refutations.
Revised slides from related talks:
Limits on Alternation-Trading Proofs for
Time-Space Bounds for Satisfiability
Templeton Foundation Infinity Project
Centre de Recerca Matematica (CRM)
February 22, 2011
Department of Computer Science
University of Swansea, Wales
March 1, 2011
Journées Complexité et Modèles Finis
Paris Diderot, Paris, France
June 22, 2011
Download slides: PDF.
Back to Sam Buss's publications page.