Super-polynomial time approximation algorithms for MAX 3SAT

Question

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.

Answer 1

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.

Answer 2

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.