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.