<p>A partial answer: as Richard Lipton outlines <a href="http://rjlipton.wordpress.com/2009/04/13/sat-is-not-too-easy/">in this post</a>, 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}$. </p>

CC BY-SA 3.0
2017-12-12T18:08:19.420Z
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
CC BY-SA 2.5
2010-08-17T04:07:21.027Z
2010-08-17T06:47:51.590Z
2010-08-17T06:47:51.590Z
Suresh Venkat
<p>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.</p>

CC BY-SA 2.5
2010-08-17T05:38:31.510Z
2010-09-19T15:11:15.157Z
2010-09-19T15:11:15.157Z
Lev Reyzin
<p>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.</p>

CC BY-SA 2.5
2010-09-07T14:45:48.000Z
2010-09-07T14:45:48.000Z
Giorgio Camerani
<p>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: <a href="http://www.cs.cmu.edu/~ryanw/automated-lbs.pdf">http://www.cs.cmu.edu/~ryanw/automated-lbs.pdf</a></p>

<p>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.</p>

<p>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.</p>

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

CC BY-SA 4.0
2019-07-23T20:44:20.607Z
@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
CC BY-SA 4.0
2019-07-24T18:39:14.463Z
@RyanWilliams Posted https://cstheory.stackexchange.com/questions/44312/time-space-trade-offs-and-towards-a-quadratic-lower-bound-for-3sat-with-m-on.
Turbo
CC BY-SA 4.0
2019-08-02T14:37:23.720Z
@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
CC BY-SA 2.5
2010-09-19T15:34:13.980Z
I don't understand what "infinitely often" means in your answer. Can you elaborate?
Vinayak Pathak
CC BY-SA 2.5
2010-09-19T17:55:30.107Z
@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
CC BY-SA 2.5
2010-10-10T19:50:44.263Z
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
CC BY-SA 2.5
2010-10-11T02:19:04.473Z
@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
CC BY-SA 2.5
2010-08-17T07:18:40.710Z
we're working on it. See this link: http://meta.cstheory.stackexchange.com/questions/3/latex-math-support
Suresh Venkat
CC BY-SA 2.5
2010-08-17T07:00:24.747Z
2010-09-07T16:38:45.117Z
2010-09-07T16:38:45.117Z
Ryan Williams
<p>What are the best current lower bounds for time and circuit depth for 3SAT?</p>

<cc.complexity-theory><lower-bounds><sat>
What are the best current lower bounds on 3SAT?
Joe Fitzsimons
# What are the best current lower bounds on 3SAT?

(Asked by: username_0 on 2010-08-17)

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

**Tags:** cc.complexity-theory, lower-bounds, sat


---

## 4 answers

### Answer by username_5 on 2010-08-17. Score: 47 | Accepted answer

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

> **Comments:**
> **username_1**: we're working on it. See this link: http://meta.cstheory.stackexchange.com/questions/3/latex-math-support  
> **username_7**: I don't understand what "infinitely often" means in your answer. Can you elaborate?  
> **username_5**: @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.  
> **username_8**: 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!  
> **username_5**: @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.  
> **username_6**: @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?  
> **username_6**: @RyanWilliams Posted https://cstheory.stackexchange.com/questions/44312/time-space-trade-offs-and-towards-a-quadratic-lower-bound-for-3sat-with-m-on.  
> **username_5**: @username_6 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.  

---

### Answer by username_1 on 2010-08-17. Score: 17

A partial answer: as Richard Lipton outlines [in this post](http://rjlipton.wordpress.com/2009/04/13/sat-is-not-too-easy/), 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 username_5, who gives a bound of the form $n^c$, where $c$ is slightly more than $\sqrt{3}$.

> **Comments:**
> **username_2**: 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  

---

### Answer by username_3 on 2010-08-17. Score: 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.


---

### Answer by username_4 on 2010-09-07. Score: 4

My understanding is the same as username_3. 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.


---

