3
$\begingroup$

I am really curious what the best-known inapproximability result is for MIN-3CNF-DELETION. To clarify, this is the problem of minimizing the number of unsatisfied clauses in a CNF SAT formula with at most 3 literals per clause. The objective function is the number of unsatisfied clauses. The strongest hardness result I have been able to find is that of MIN-HORN-DELETION, which is a restricted variant of MIN-3CNF-DELETION. As far as I know the best-known inapproximability result for MIN-HORN-DELETION is that which is given in The Approximability of Constraint Satisfaction Problems by Khanna et al (2000).

However, I have not yet been able to find explicit references to MIN-3CNF-DELETION. Is it even harder than MIN-HORN-DELETION? In which case, what is the best known inapproximability threshhold? Any feedback would be most welcome. Thanks!

$\endgroup$
  • $\begingroup$ It is not even possible to determine in polynomial time whether a 3 CNF SAT is satisfiable or not (if P≠NP). That is, it is not possible to determine if the objective function is equal to 0 or strictly positive. So there is no approximation algorithm for MIN-3CNF-DELETION at all. $\endgroup$ – Yury Oct 10 '12 at 15:47
  • $\begingroup$ In contrast, if an instance of Min-Horn-Deletion or Min-2CNF-Deletion (or say Unique Games) is completely satisfiable, we can efficiently find a solution that satisfies all clauses (constraints). Thus it makes sense to talk about approximation algorithms for Min-Horn-Deletion and Min-2CNF-Deletion. $\endgroup$ – Yury Oct 10 '12 at 15:52
8
$\begingroup$

There is no approximation algorithm for MIN-3CNF-DELETION at all since it is not even possible to determine in polynomial time whether a 3 CNF SAT instance is satisfiable or not (if P≠NP). That is, it is not possible to determine if the objective function is equal to 0 or strictly positive. Specifically, if we had an $f(n)$ approximation algorithm for the problem, given a satisfiable instance the algorithm would find a solution of cost $0 \cdot f(n) = 0$ ; that is, a solution that satisfies the instance.

In contrast, if an instance of Min-Horn-Deletion or Min-2CNF-Deletion is (completely) satisfiable, we can efficiently find a solution that satisfies all clauses. Thus it makes sense to talk about approximation algorithms for Min-Horn-Deletion and Min-2CNF-Deletion.

$\endgroup$
  • $\begingroup$ but you could expect a result that addresses only unsat instances, e.g., it's NP-hard to distinguish between the case where it suffices to delete delta fraction of the clauses, and the the case where you have to delete alpha fraction of the clauses (for some appropriate alpha, delta). $\endgroup$ – Dana Moshkovitz Oct 11 '12 at 16:02
  • $\begingroup$ @DanaMoshkovitz, you are right. This problem is also not approximable in this sense. Håstad showed that we cannot satisfy more than a $7/8 + \varepsilon$ fraction of constraints even if the instance is satisfiable. That is, it's NP hard to distinguish between the case where it suffices to delete a $\delta \geq 0$ fraction of the clauses, and the the case where we have to delete $\alpha = 1/8 - \varepsilon$ fraction of the clauses. $\endgroup$ – Yury Oct 11 '12 at 16:28
4
$\begingroup$

The problem MIN-3CNF-DELETION you refer to is better known as MAX-3CNF-SAT (or simply MAX-3SAT for short). Presented as a decision problem, it's the problem of determining (for any input value m) whether there exists an assignment which satisfies at least m of the CNF clauses; presented as an optimization problem, it's the problem of determining the maximum number of clauses which any assignment may satisfy.

This presentation as an optimization problem is clearly complementary to the problem you describe, and (unlike MIN-3CNF-DELETION), it makes sense to consider the feasibility of approximation versions of the problem with multiplicative error because the most extreme value isn't zero. In fact, MAX-3-SAT cannot be approximated to within a constant factor better than 7/8 (unless P = NP). Furthermore, Karloff and Zwick demonstrated that there does exist an approximation algorithm achieving that upper bound.

Edited to add. The business with the approximation factor in Karloff and Zwick's result seems to be somewhat more complicated than it appears. Many papers in the literature describe their result simply as a 7/8-approximation algorithm. However, Zwick himself writes the following in a footnote on page 1 of this paper:

More precisely, [KZ97] obtain a $(7/8 - \epsilon)$-approximation algorithm for satisfiable instances of MAX-3SAT and provide compelling analytical and numerical evidence that suggest that the performance ratio of the algorithm is $7/8-\epsilon$ for all instances of the problem, for every $\epsilon > 0$. It is possible to show that the $\epsilon$ in the above expressions can be eliminated.

$\endgroup$

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.