Extended Abstract:

    Sam Buss
    "Alternation-Trading Proofs and Their Limits
    In Proc. 38th International Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science 8087, Springer-Verlag, pp. 1-7, 2013.

    See also the paper by S. Buss and R. Williams .

    Download the conference paper: PDF.

    Download slides from MFCS'31 conference talk: PDF slides.

Abstract:  Alternation trading proofs are motivated by the goal of separating NP from complexity classes such as \Logspace or NL; they have been used to give super-linear runtime bounds for deterministic and co-nondeterministic sublinear space algorithms which solve the Satisfiability problem. For algorithms which use n^{o(1)} space, alternation trading proofs can show that deterministic algorithms for Satisfiability require time greater than n^{cn} for c<2\cos(\pi/7) (as shown by Williams), and that co-nondeterministic algorithms require time greater than n^{cn} for c<\sqrt[3]{4} (as shown by Diehl, van Melkebeek and Williams). It is open whether these values of c are optimal, but Buss and Williams have shown that for deterministic algorithms, c<2\cos(\pi/7) is the best that can obtained using present-day known techniques of alternation trading.
    This talk will survey alternation trading proofs, and discuss the optimality of the unlikely value of 2\cos(\pi/7).

Back to Sam Buss's publications page.