51

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

Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106
Joe Fitzsimons
  • 13,675
  • 47
  • 91

4 Answers4

47

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

Ryan Williams
  • 27,465
  • 7
  • 115
  • 164
  • 2
    we're working on it. See this link: http://meta.cstheory.stackexchange.com/questions/3/latex-math-support – Suresh Venkat Aug 17 '10 at 07:18
  • I don't understand what "infinitely often" means in your answer. Can you elaborate? – Vinayak Pathak Sep 19 '10 at 15:34
  • 2
    @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
  • 2
    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
  • 2
    @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 02:19
  • @RyanWilliams I think OP asks $3SAT$ which can be $NP$ complete with just $n=O(m)$ clauses where $m$ is number of variables. I think the lower bound is for $SAT$ with $n=\omega(m)$ clauses. 1. Is it not true? Then what is best lower bound for $3SAT$ with $n=O(m)$ clauses? 2. Also is there a lower bound on $K$ with $KSAT$ having just $n=O(m)$ clauses give very fast algorithms that could beat $ETH$? 3. Is there trade off between $m$ number of variables and $n$ number of clauses that indicates difficulty of $SAT$ instance? Is there similar trade-offs? – Turbo Jul 23 '19 at 20:44
  • @RyanWilliams Posted https://cstheory.stackexchange.com/questions/44312/time-space-trade-offs-and-towards-a-quadratic-lower-bound-for-3sat-with-m-on. – Turbo Jul 24 '19 at 18:39
  • 1
    @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 02 '19 at 14:37
17

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}$.

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

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.

Lev Reyzin
  • 11,968
  • 13
  • 63
  • 103
4

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.

Giorgio Camerani
  • 6,842
  • 1
  • 34
  • 64