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

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

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

CC BY-SA 3.0
2015-03-04T04:16:24.437Z
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...)
Ryan Williams
CC BY-SA 3.0
2015-03-04T13:04:52.910Z
Sorry about that. Ryan is of course correct.
Thomas Ahle
<cc.complexity-theory><approximation-algorithms><sat><approximation-hardness><exp-time-algorithms>
Is MAX-SAT SETH (like) hard?
Thomas Ahle
# Is MAX-SAT SETH (like) hard?

(Asked by: username_0 on 2015-03-03)

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?

**Tags:** cc.complexity-theory, approximation-algorithms, sat, approximation-hardness, exp-time-algorithms
> **Comments:**
> **username_1**: 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...)  
> **username_0**: Sorry about that. Ryan is of course correct.  

---

## 0 answers

