Let $L_\epsilon$ be the language of all $2$-CNF formulas $\varphi$, such that at least $(\frac{1}{2}+\epsilon)$ of $\varphi$'s clauses can be satisfied.

I need to prove that there exists $\epsilon'$ s.t $L_\epsilon$ is $\mathsf{NP}$-hard for any $\epsilon<\epsilon'$.

We know that $\text{Max}2\text{Sat}$ can be approximate to $\frac{55}{56}$ precent of the clauses from a $\text{Max}3\text{Sat}$ reduction. How should I solve this one?


In his famous paper, Håstad shows that it is NP-hard to approximate MAX2SAT better than $21/22$. This likely means that is is NP-hard to distinguish instances which are $\leq \alpha$ satisfiable and instances which are $\geq (22/21) \alpha$ satisfiable, for some $\alpha \geq 1/2$. Now imagine padding an instance so that it becomes a $p$-fraction of a new instance, the rest of which is exactly $1/2$-satisfiable (say it consists of groups of clauses of the form $a \land \lnot a$). The numbers now become $1/2 + p (\alpha - 1/2)$ and $1/2 + p((22/21)\alpha - 1/2)$. The latter number can be made as close to $1/2$ as we want.

  • $\begingroup$ Does your method works when ε is an arbitrary (but sufficiently small) real number? I cannot figure out how to choose the appropriate number of clauses to use for padding unless I assume something about ε. (Note that ε is not part of the input, and therefore it is well-defined to consider real number ε.) $\endgroup$ Dec 22 '12 at 23:10
  • $\begingroup$ That's where the gap between $1/2+p(\alpha-1/2)$ and $1/2+p((22/21)\alpha-1/2)$ could be useful. Assuming $\alpha$ is rational, take some rational $p$, and you should do fine. $\endgroup$ Dec 23 '12 at 1:04
  • $\begingroup$ Aha, somehow I thought that that method did not work when I tried it first, but now I see how it works. Thanks! $\endgroup$ Dec 23 '12 at 1:26

If you know that ε is a rational number, then you do not need inapproximability for Max-2-SAT to prove your statement. A typical proof of the NP-hardness of Max-2-SAT (e.g., the one in the textbook Computational Complexity by Papadimitriou) actually proves the NP-completeness of L1/5. To prove the NP-hardness of Lε for positive rational numbers ε<1/5, we can reduce L1/5 to Lε as follows: given a 2CNF formula φ (an instance for L1/5), let m be the number of clauses in it. Let r and s be positive integers such that (1/5−ε)mr = 2εs holds. Then construct a 2CNF formula (an instance for Lε) by repeating φ for r times and adding s pairs of contradicting clauses. A simple calculation shows that this is indeed a reduction from L1/5 to Lε.

This reduction clearly works only if ε is rational, because otherwise r and s cannot be taken as integers. The general case where ε is not necessarily rational seems to require inapproximability, as Yuval Filmus wrote in his answer.


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.