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