20
$\begingroup$

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.

$\endgroup$
29
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Mohammad Al-Turkistany Dec 9 '11 at 12:29
18
$\begingroup$

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.

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