Article:

    Samuel R. Buss and Ryan Williams.
    "Limits on Alternation-Trading Proofs for Time-Space Lower Bounds"
    Computational Complexity 24, 3 (2015) 533-600.
    DOI: 10.1007/s00037-015-0104-9
    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: PDF, 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)
   Barcelona, Spain
   February 22, 2011
and
   Department of Computer Science
   University of Swansea, Wales
   March 1, 2011

and
   Journées Complexité et Modèles Finis
   Paris Diderot, Paris, France
   June 22, 2011

  Download slides: PDF.

Back to Sam Buss's publications page.