# Hardness of Approximation of MAX-3SAT

This is probably a duplicate of this question, but I need a somewhat blunter answer. Let's say I have a polynomial time algorithm that finds an assignment that satisfies more than $\frac{7}{8}$ of the clauses of a satisfiable 3SAT instance. Do I collect my million dollars from the Clay Institute for proving $P=NP$?

## 1 Answer

I believe that Håstad gave such an algorithm in 2000, see On bounded occurrence constraint satisfaction. His algorithm is stated for instances where each variable occurs at most $B$ times, and the advantage over 7/8 depends on $B$. The running time, however, seems not to depend on $B$.

In order to prove that P=NP, you need to find an algorithm which, given a satisfiable instance, satisfies at least $7/8+\epsilon$ clauses, for some constant $\epsilon>0$. This will enable you to distinguish between satisfiable instances and instances which are at most $7/8+\epsilon/2$ satisfiable, which is NP-hard as my answer to the question you mention shows.

• I think I understand the difference, but now I'm further mystified. Let's say my hypothetical algorithm finds an assignment that satisfies 90% of the clauses for a satisfiable instance. Now it is presented with a problem where the maximum proportion of satisfiable clauses is, like, 95%. How would my 90% algorithm distinguish between the two? – Andrew Mar 2 '17 at 12:54
• Your algorithm doesn't distinguish between these two cases. It distinguishes (for example) between satisfiable instances and those that are at most 89% satisfiable. – Yuval Filmus Mar 2 '17 at 12:57
• Aha, I think I get it. To keep it concrete, distinguishing between 7/8th satisfiable and 100% satisfiable is in P, distinguishing between 89% satisfiable and 100% satisfiable is NP-hard (where that 89% is constant and independent of the problem). You could use my hypothetical 90% solver to solve the real satisfiability problem by reducing an input formula $\phi$ in polynomial time to another formula $\phi'$ such that $\phi'$ is 90% satisfied iff $\phi$ is SAT. But if you can only achieve 7/8th, then you have gained nothing. – Andrew Mar 2 '17 at 14:05
• Right, you got it. It is actually conceivable that 89% or 90% could be improved to $7/8+f(n)$ for some $f(n)=o(1)$, but I'm not aware of any such result in the literature, and I don't know whether current technology is good enough to prove such a bound. – Yuval Filmus Mar 2 '17 at 14:12