If we make a random assignment to the variables in $k$-sat ($m$ clauses), we are going to satisfy $(1-2^{-k})m$ clauses in expectation. In general satisfying fewer clauses is considered easy.

There are newer algorithms for 3-sat that satisfy $(1-1/8+\epsilon)m$ clauses in $O(2^{8\epsilon m})$ time. I'm wondering if it's believed that this sort of result is tight in spirit of SETH?

In other words, does it seem reasonable to believe, say, that for any $\delta>0$ there exists $k$ so satisfying $(1-2^{-k}+\epsilon)m$ clauses in $k$-sat takes $\Omega((2-\delta)^{2^k\epsilon m})$ time?

  • 1
    $\begingroup$ You quantified over $\delta$ but didn't make any further reference to it. $\;$ $\endgroup$
    – user6973
    Mar 4, 2015 at 2:23
  • 2
    $\begingroup$ Probably he means: for every $\delta > 0$ there is a k such that max k sat $(1-1/2^k + \varepsilon)$-approximation needs at least $(2-\delta)^{2^k \varepsilon m}$ time. (Don't think this is true...) $\endgroup$ Mar 4, 2015 at 4:16
  • $\begingroup$ Sorry about that. Ryan is of course correct. $\endgroup$ Mar 4, 2015 at 13:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.