Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 9 down vote accepted

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.

share|improve this answer
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
add comment

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.