<p>To somewhat restate what Ryan Williams wrote in his last paragraph: </p>

<p>The Moshkovitz-Raz theorem shows that there is a function $T(n) = 2^{n^{1-o(1)}}$ such that if Max-3Sat can be $(7/8 + 1/(\log \log n)^{.000001})$-approximated in time $T(n)$ then the decision version of 3Sat is in time $2^{o(n)}$.  It is commonly believed that the latter is impossible (this is the Exponential Time Hypothesis), in which case the former is impossible too.  To put it not quite accurately, you can't beat $7/8$ for Max-3Sat in anything better than full exponential time.</p>

CC BY-SA 3.0
2011-12-09T20:38:35.397Z
2011-12-09T20:38:35.397Z
Ryan O'Donnell
<p>One can get a $7/8+\varepsilon/8$ approximation for MAX3SAT that runs in $2^{O(\varepsilon n)}$ time without too much trouble. Here is the idea. Divide the set of variables into $O(1/\varepsilon)$ groups of $\varepsilon n$ variables each. For each group, try all $2^{\varepsilon n}$ ways to assign the variables in the group. For each reduced formula, run the Karloff and Zwick $7/8$-approximation. Output the assignment satisfying a maximum number of clauses, out of all these trials.</p>

<p>The point is that there is some variable block such that the optimal assignment (restricted to that block) already satisfies a $\varepsilon$-fraction of the maximum number of satisfied clauses. You'll get those extra clauses exactly correct, and you'll get $7/8$ of the the remaining fraction of the optimum using Karloff and Zwick.</p>

<p>It is an interesting question if one can get $2^{O(\varepsilon^2 n)}$ time for the same type of approximation. There is a "Linear PCP Conjecture" that 3SAT can be reduced in polynomial time to MAX3SAT, such that:</p>

<ul>
<li>if the 3SAT instance is satisfiable then the MAX3SAT instance is completely satisfiable,</li>
<li>if the 3SAT instance is unsatisfiable then the MAX3SAT instance isn't $7/8+\varepsilon$ satisfiable, and</li>
<li>the reduction increases the formula size by only a $poly(1/\varepsilon)$ factor. </li>
</ul>

<p>Assuming this Linear PCP Conjecture, a $2^{O(\varepsilon^c m)}$-time $7/8+\varepsilon$ approximation, for all $c$ and $\varepsilon$, would entail that 3SAT is in $2^{\varepsilon n}$ time, for all $\varepsilon$. (Here $m$ is the number of clauses.) The proof uses the Sparsification Lemma of Impagliazzo, Paturi, and Zane.</p>

CC BY-SA 3.0
2011-12-09T12:29:11.447Z
Thanks Rayan for your nice answer, Can we take this as an evidence against the existence of quasi-polynomial or sub-exponential time algorithms with approximation ratios better than $7/8$?
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-12-08T21:48:43.763Z
2011-12-09T21:57:56.653Z
2011-12-09T21:57:56.653Z
Ryan Williams
<p>The PCP theorem states that there is no polynomial time algorithm for MAX 3SAT to find an assignment satisfying $7/8+ \epsilon$ clauses of a satisfiable 3SAT formula unless $P = NP$.</p>

<p>There is a trivial polynomial time algorithm that satisfies $7/8$ of the clauses. So, Can we do better than $7/8+ \epsilon $ if we allow super-polynomial algorithms?  What approximation ratios can we achieve  with quasi-polynomial time algorithms ( $n^{O(\log n)}$) or with sub-exponential time algorithms($2^{o(n)}$)? I'm looking for references to any such algorithms.</p>

<cc.complexity-theory><pcp>
Super-polynomial time approximation algorithms for MAX 3SAT
Mohammad Al-Turkistany
# Super-polynomial time approximation algorithms for MAX 3SAT

(Asked by: username_0 on 2011-12-08)

The PCP theorem states that there is no polynomial time algorithm for MAX 3SAT to find an assignment satisfying $7/8+ \epsilon$ clauses of a satisfiable 3SAT formula unless $P = NP$.

There is a trivial polynomial time algorithm that satisfies $7/8$ of the clauses. So, Can we do better than $7/8+ \epsilon $ if we allow super-polynomial algorithms? What approximation ratios can we achieve with quasi-polynomial time algorithms ( $n^{O(\log n)}$) or with sub-exponential time algorithms($2^{o(n)}$)? I'm looking for references to any such algorithms.

**Tags:** cc.complexity-theory, pcp

---

## 2 answers

### Answer by username_2 on 2011-12-08. Score: 32 | Accepted answer

One can get a $7/8+\varepsilon/8$ approximation for MAX3SAT that runs in $2^{O(\varepsilon n)}$ time without too much trouble. Here is the idea. Divide the set of variables into $O(1/\varepsilon)$ groups of $\varepsilon n$ variables each. For each group, try all $2^{\varepsilon n}$ ways to assign the variables in the group. For each reduced formula, run the Karloff and Zwick $7/8$-approximation. Output the assignment satisfying a maximum number of clauses, out of all these trials.

The point is that there is some variable block such that the optimal assignment (restricted to that block) already satisfies a $\varepsilon$-fraction of the maximum number of satisfied clauses. You'll get those extra clauses exactly correct, and you'll get $7/8$ of the the remaining fraction of the optimum using Karloff and Zwick.

It is an interesting question if one can get $2^{O(\varepsilon^2 n)}$ time for the same type of approximation. There is a "Linear PCP Conjecture" that 3SAT can be reduced in polynomial time to MAX3SAT, such that:

* if the 3SAT instance is satisfiable then the MAX3SAT instance is completely satisfiable,
* if the 3SAT instance is unsatisfiable then the MAX3SAT instance isn't $7/8+\varepsilon$ satisfiable, and
* the reduction increases the formula size by only a $poly(1/\varepsilon)$ factor.

Assuming this Linear PCP Conjecture, a $2^{O(\varepsilon^c m)}$-time $7/8+\varepsilon$ approximation, for all $c$ and $\varepsilon$, would entail that 3SAT is in $2^{\varepsilon n}$ time, for all $\varepsilon$. (Here $m$ is the number of clauses.) The proof uses the Sparsification Lemma of Impagliazzo, Paturi, and Zane.

> **Comments:**
> **username_0**: Thanks Rayan for your nice answer, Can we take this as an evidence against the existence of quasi-polynomial or sub-exponential time algorithms with approximation ratios better than $7/8$?  

---

### Answer by username_1 on 2011-12-09. Score: 18

To somewhat restate what Ryan Williams wrote in his last paragraph:

The Moshkovitz-Raz theorem shows that there is a function $T(n) = 2^{n^{1-o(1)}}$ such that if Max-3Sat can be $(7/8 + 1/(\log \log n)^{.000001})$-approximated in time $T(n)$ then the decision version of 3Sat is in time $2^{o(n)}$. It is commonly believed that the latter is impossible (this is the Exponential Time Hypothesis), in which case the former is impossible too. To put it not quite accurately, you can't beat $7/8$ for Max-3Sat in anything better than full exponential time.


---

