46
$\begingroup$

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

$\endgroup$
43
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ we're working on it. See this link: meta.cstheory.stackexchange.com/questions/3/latex-math-support $\endgroup$ – Suresh Venkat Aug 17 '10 at 7:18
  • $\begingroup$ I don't understand what "infinitely often" means in your answer. Can you elaborate? $\endgroup$ – Vinayak Pathak Sep 19 '10 at 15:34
  • 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$ – Ryan Williams Sep 19 '10 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$ – Warren Schudy Oct 10 '10 at 19:50
  • 1
    $\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$ – Ryan Williams Oct 11 '10 at 2:19
17
$\begingroup$

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

$\endgroup$
  • 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$ – Dan Brumleve Dec 12 '17 at 18:08
10
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.