The PCP theorem implies (with other results) that there is no polynomial time algorithm for MAX 3SAT to find an assignment satisfying $7/8+ \epsilon$ clauses of a satisfiable 3SAT formula unless $P = NP$.

There is a trivial polynomial time algorithm that satisfies $7/8$ of the clauses. How hard is it to find an assignment that satsfies at least $7/8$ of the clauses but no more than $7/8 +\epsilon $ for some $\epsilon \gt 0$? Is this task still $NP$-hard?

  • $\begingroup$ Such an assignment doesn't always exist. When you see NP-hard, do you mean that you want to decide whether such an assignment exists? $\endgroup$ – Yuval Filmus Jun 26 '13 at 16:08
  • $\begingroup$ I guess the search problem reduces to the decision problem but yes I would like to know whether the decision problem is NP-hard. $\endgroup$ – Mohammad Al-Turkistany Jun 26 '13 at 16:14

The PCP theorem states that for every $\delta > 0$, it is NP-hard to decide whether a 3CNF is satisfiable or at most $(7/8+\delta)$-satisfiable. Take such a formula $\varphi$ and add to it lots of copies of $(a \lor b \lor c) \land \cdots \land (\lnot a \lor \lnot b \lor \lnot c)$, where $a,b,c$ are new variables (by $\cdots$ I mean eight clauses, exactly seven of which are always satisfied). Suppose these clauses take up $(1-\epsilon)$ of the new 3CNF. This replaces the original $1$ vs. $7/8 + \delta$ to $\epsilon + (1-\epsilon)7/8$ vs. $(7/8+\delta)\epsilon + (1-\epsilon)7/8$, that is $7/8 + \epsilon/8$ vs. $7/8 + \delta\epsilon$. That's not exactly what you wanted since $\delta \neq 0$, but it's pretty close.

| cite | improve this answer | |

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.