<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2012-10-11T16:02:57.127Z
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).
Dana Moshkovitz
CC BY-SA 3.0
2012-10-11T16:28:42.850Z
@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.
Yury
CC BY-SA 3.0
2012-10-10T16:01:45.427Z
2012-10-10T16:17:57.230Z
2012-10-10T16:17:57.230Z
Yury
<p>The problem MIN-3CNF-DELETION you refer to is better known as MAX-3CNF-SAT (or simply <a href="http://en.wikipedia.org/wiki/MAX-3SAT" rel="nofollow">MAX-3SAT</a> for short). Presented as a decision problem, it's the problem of determining (for any input value <em>m</em>) whether there exists an assignment which satisfies at least <em>m</em> 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.</p>

<p>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, <a href="http://en.wikipedia.org/wiki/MAX-3SAT#Theorem_2" rel="nofollow">MAX-3-SAT cannot be approximated to within a constant factor better than 7/8</a> (unless <strong>P</strong>&nbsp;=&nbsp;<strong>NP</strong>). Furthermore, Karloff and Zwick demonstrated that there does exist <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1351" rel="nofollow">an approximation algorithm achieving that upper bound</a>. </p>

<p><strong>Edited to add.</strong> 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 <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.2193" rel="nofollow">this paper</a>:  </p>

<blockquote>
  <p>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 <em>all</em> instances of the problem, for every $\epsilon &gt; 0$. It is possible to show that the $\epsilon$ in the above expressions can be eliminated.</p>
</blockquote>

CC BY-SA 3.0
2012-10-11T15:37:55.410Z
2012-10-11T16:58:30.927Z
2012-10-11T16:58:30.927Z
Niel de Beaudrap
<p>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). </p>

<p>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!</p>

CC BY-SA 3.0
2012-10-10T15:47:27.253Z
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.
Yury
CC BY-SA 3.0
2012-10-10T15:52:14.050Z
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.
Yury
<cc.complexity-theory><ds.algorithms><sat><approximation-hardness>
What is the best-known inapproximability result for MIN-3CNF-DELETION?
Steven Kelk
# What is the best-known inapproximability result for MIN-3CNF-DELETION?

(Asked by: username_0 on 2012-10-10)

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!

**Tags:** cc.complexity-theory, ds.algorithms, sat, approximation-hardness

> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  

---

## 2 answers

### Answer by username_1 on 2012-10-10. Score: 8

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.

> **Comments:**
> **username_2**: 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).  
> **username_1**: @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.  

---

### Answer by username_3 on 2012-10-11. Score: 4

The problem MIN-3CNF-DELETION you refer to is better known as MAX-3CNF-SAT (or simply [MAX-3SAT](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/MAX-3SAT#Theorem_2) (unless **P** = **NP**). Furthermore, Karloff and Zwick demonstrated that there does exist [an approximation algorithm achieving that upper bound](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1351).

**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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.2193):

> 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.


---

