# Find $\epsilon'$ s.t $L_\epsilon$ is $\mathsf{NP}$-hard for any $\epsilon<\epsilon'$

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?

## 2 Answers

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.

• 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 ε.) Dec 22 '12 at 23:10
• 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. Dec 23 '12 at 1:04
• Aha, somehow I thought that that method did not work when I tried it first, but now I see how it works. Thanks! 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.