# What are the best current lower bounds on 3SAT?

What are the best current lower bounds for time and circuit depth for 3SAT?

As far as I know, the best known "model-independent" time lower bound for SAT is the following. Let $T$ and $S$ be the running time and space bound of any SAT algorithm. Then we must have $T \cdot S \geq n^{2 \cos(\pi/7) - o(1)}$ infinitely often. Note $2 \cos(\pi/7) \approx 1.801$. (The result that Suresh cites is a little obsolete.) This result appeared in STACS 2010, but that is an extended abstract of a much longer paper, which you can get here: http://www.cs.cmu.edu/~ryanw/automated-lbs.pdf

Of course, the above work builds on a lot of prior work which is mentioned in Lipton's blog (see Suresh's answer). Also, as the space bound S gets close to n, the time lower bound T gets close to n as well. You can prove a better "time-space tradeoff" in this regime; see Dieter van Melkebeek's survey of SAT time-space lower bounds from 2008.

If you restrict yourself to multitape Turing machines, you can prove $T \cdot S \geq n^{2-o(1)}$ infinitely often. That was proved by Rahul Santhanam, and follows from a similar lower bound that's known for PALINDROMES in this model. We believe you should be able to prove a quadratic lower bound that is "model-independent" but that has been elusive for some time.

For non-uniform circuits with bounded fan-in, I know of no depth lower bound better than $\log n$.

• we're working on it. See this link: meta.cstheory.stackexchange.com/questions/3/latex-math-support – Suresh Venkat Aug 17 '10 at 7:18
• @vinayak: The statement in which "infinitely often" appears in the above is the negation of: "There is a SAT algorithm such that $T \cdot S \leq n^{2 \cos(\pi/7)+o(1)}$, almost everywhere." The negation of "almost everywhere" is "infinitely often", it means that for every algorithm there are infinitely many instances on which it fails to solve the instance with a small product of time and space. – Ryan Williams Sep 19 '10 at 17:55
• It's amazing that we have better lower bounds on $T \cdot S$ for the really easy problem of element distinctness ($T \cdot S = \Omega(n^{2-o(1)})$ by Yao) than we do for SAT! – Warren Schudy Oct 10 '10 at 19:50
• @Warren, not quite, as far as I know. Lower bounds like Yao are for the comparison-based branching program model, which is not nearly as expressive as a general purpose random access machine. One could imagine solving element distinctness without any direct comparisons between elements at all. – Ryan Williams Oct 11 '10 at 2:19
• @Turbo the best lower bound for 3sat with linearly many clauses is the same as what I wrote, because the reduction from sat to 3sat is extremely local. Reading the literature on the topic will also show this. – Ryan Williams Aug 2 at 14:37

A partial answer: as Richard Lipton outlines in this post, the best bounds are time-space tradeoffs, that ask for a lower bound on time with space $o(n)$. The best known bound in this vein is due to Ryan Williams, who gives a bound of the form $n^c$, where $c$ is slightly more than $\sqrt{3}$.

• I think the bound is really $n^{o(1)}$ space, not $o(n)$ space. See the abstract of Williams' paper: cs.cmu.edu/~ryanw/ccc05.pdf – Dan Brumleve Dec 12 '17 at 18:08

My understanding is that, without additional assumptions, we do not have a superlinear time, as in $\Omega(n^c)$ for constant $c > 1$, lower bound for 3SAT.

My understanding is the same as Lev Reyzin. It is possible that there exists a deterministic complete algorithm for SAT which runs in space O(n) and in time O(n). It's amazing that the existence of such an efficient algorithm is not prohibited.