__Extended Abstract:__

**
Sam Buss
"Alternation-Trading Proofs and Their Limits
In **

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).