# 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?

-

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 ε.) –  Tsuyoshi Ito 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. –  Yuval Filmus 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! –  Tsuyoshi Ito Dec 23 '12 at 1:26