What are the best current lower bounds for time and circuit depth for 3SAT?
$\begingroup$
$\endgroup$
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
8
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$.
answered Aug 17, 2010 at 7:00
-
2$\begingroup$ we're working on it. See this link: meta.cstheory.stackexchange.com/questions/3/latex-math-support $\endgroup$ Commented Aug 17, 2010 at 7:18
-
2$\begingroup$ @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. $\endgroup$ Commented Sep 19, 2010 at 17:55
-
2$\begingroup$ 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! $\endgroup$ Commented Oct 10, 2010 at 19:50
-
2$\begingroup$ @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. $\endgroup$ Commented Oct 11, 2010 at 2:19
-
1$\begingroup$ @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. $\endgroup$ Commented Aug 2, 2019 at 14:37
$\begingroup$
$\endgroup$
1
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}$.
answered Aug 17, 2010 at 4:07
-
1$\begingroup$ 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 $\endgroup$ Commented Dec 12, 2017 at 18:08
$\begingroup$
$\endgroup$
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.
answered Aug 17, 2010 at 5:38
$\begingroup$
$\endgroup$
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.
answered Sep 7, 2010 at 14:45