Lower Bounds for Satisfiability and Related Problems (a survey)
by Dieter van Melkebeek
Oded's comments
Let me augment the high-level abstract by the taste of the actual results.
Loosely speaking, the main such result states that
for every $c \leq d$ such that either $(c-1)d<1$ or $(d-1)cd-2d < 1$
there exists a $e>0$
such that SAT is not in the intersection
of $DTime[n^c]$ and $DTiSp[n^d,n^e]$.
For example, one may conclude that SAT is not in the intersection
of $DTime[n^{1+o(1)}]$ and $DTiSp[poly(n),n^{o(1)}] \sperseteq L$.
The proof typically proceeds by assuming, towards the contradiction,
that $NTime[n]$ is contained in both $coNTime[n^c]$
and $DTiSp[n^d,n^e]$, and derives a contradiction by using
(1) time speedup (for DTiSp) via alternation,
and (2) eliminating alternation by using the 1st hypothesis.
Specifically, a "DTiSp[t,s]-computation" can be encoded by
a statement of the form "there exists $b-1$ intermediate
configurations such that for every $i\in[b-1]$ the $i$th
follows from the $i-1$st in $t/b$ steps",
which yields a Sigma2 computation with time $bs+(t/b)$
(which equals $2sqrt(ts)$ when $b=sqrt(t/s)$).
We can also get a Pi2 expression by considering the negation.
On the other hand, using $NTime[t] \subseteq coNTime[t^c]$,
we derive $Pi2Time[t] \subseteq coPi1Time[(n+t)^c]$.
Combining both we get $DTiSp[t,t^{o(1)}] \subseteq coNTime[t^{c/2}]$,
which implies
$NTime[n] \subseteq DTiSp[n^d,n^{o(1)}] \subseteq coNTime[t^{dc/2}]$
(yieling a contradiction for $cd < 2$).
The original abstract
Ever since the work of Cook and Levin, satisfiability has been
recognized as a central problem in computational complexity.
It is widely believed to be intractable,
and yet till recently even a linear-time logarithmic-space
algorithm was not ruled out.
The last few years have seen considerable progress in time-space lower bounds
for satisfiability and closely related problems on various models of
computation. This talk will describe the state-of-the-art on deterministic,
randomized, and quantum machines, survey the underlying ideas, and
present some of the arguments involved.
Back to
list of Oded's choices.