Limits on Alternation Trading

Preprint:

    Samuel R. Buss and Ryan Williams.
    "Limits on Alternation-Trading Proofs for Time-Space Lower Bounds"
    ECCC Technical Report TR11-031. March 8, 2011.
    Preliminary manuscript, 2011.

Download manuscript: PDF.

Abstract: This paper characterizes alternation trading based proofs that satisfiability is not in the time and space bounded class DTISP(n^c,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 simulationl runtimes for searching for DTISP alternation trading refutations.

Revised slides from related talk:

   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.