4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Andrew Mar 2 '17 at 12:54
  • $\begingroup$ Your algorithm doesn't distinguish between these two cases. It distinguishes (for example) between satisfiable instances and those that are at most 89% satisfiable. $\endgroup$ – Yuval Filmus Mar 2 '17 at 12:57
  • 1
    $\begingroup$ 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. $\endgroup$ – Andrew Mar 2 '17 at 14:05
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 2 '17 at 14:12

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.