MAX-E3SAT is a problem that finds a truth value assignment that satisfies the maximum number of clauses for a given a set of clause which contains exactly three literals.
MAX-2SAT is a problem that finds a truth value assignment that satisfies the maximum number of clauses for a given a set of clauses which contains at most two literals.
Then there exists a $\frac{7}{8}$-approximation algorithm for MAX-E3SAT problem.
Proof is like follow. If you see all of the clauses and count the existance of each literals and complementary of literals. Then, we can pick at least half of them to be satisfied by pick $x_i$ or $\overline{x_i}$. Then, we can cover at least $\frac{7}{8}$ of them because we have three literals for one clauses.
Then, P=NP if there exists a $(\frac{7}{8} + \epsilon)$-approximation algorithm for MAX-E3SAT problem for all constant $\epsilon > 0$.
Proof will be updated later.
Then there exists no $\alpha$-approximation for MAX 2SAT for any constant $\alpha > \frac{433}{440}$ unless P=NP.
Proof is like follow.
First of all, let’s think about follow.
For three literals $l1$, $l2$ and $l3$, consider the follwing set of ten clauses in terms of $l1, l2, l3$ and auxiliary variable $y$.
- $l1$
- $l2$
- $l3$
- $\overline{l1}\lor\overline{l2}$
- $\overline{l2}\lor\overline{l3}$
- $\overline{l1}\lor\overline{l3}$
- $y$
- $l1\lor\overline{y}$
- $l2\lor\overline{y}$
- $l3\lor\overline{y}$
If $l1 \lor l2 \lor l3$ is satisfied, we can choose the value of $y$ so that exactly seven of the ten clauses are satisfied and it is impossible to satisfy more than that. If $l1 \lor l2 \lor l3$ is not satisfied, we can choose the value of $y$ so that exactly six of the ten clauses are satisfied and it is impossible to satisfy more than that.
Notice that we can have following table with number of satisfied clauses if $y$ is true.
| # true literals | # true clauses in 1~3 | # true clauses in 4~6 | # true clauses in 7~10 | # true clauses in Total |
|---|---|---|---|---|
| 3 | 3 | 0 | 4 | 7 |
| 2 | 2 | 2 | 3 | 7 |
| 1 | 1 | 3 | 2 | 6 |
| 0 | 0 | 3 | 1 | 4 |
If $y$ is false then number of satisfied clauses is like below.
| # true literals | # true clauses in 1~3 | # true clauses in 4~6 | # true clauses in 7~10 | # true clauses in Total |
|---|---|---|---|---|
| 3 | 3 | 0 | 3 | 6 |
| 2 | 2 | 2 | 3 | 7 |
| 1 | 1 | 3 | 3 | 7 |
| 0 | 0 | 3 | 3 | 6 |
As a result, maximum is follow.
| # true literals | # true clauses in 1~3 | # true clauses in 4~6 | # true clauses in 7~10 (best) | # true clauses in Total(best) |
|---|---|---|---|---|
| 3 | 3 | 0 | 4 ($y$ as true) | 7 |
| 2 | 2 | 2 | 3 ($y$ as true/false) | 7 |
| 1 | 1 | 3 | 3 ($y$ as false) | 7 |
| 0 | 0 | 3 | 3 ($y$ as false) | 6 |
Now. think about $m$ clauses that consistes an instance of the MAX E3SAT problem with $n$ varaibles. We construct a MAX 2SAT instance by follow.
For each $j$th clause in MAX E3SAT problem, make 10 clauses with distinct auxiliary varaible in the algorithm above. Then, set $l1$, $l2$, $l3$ as each literals used in $j$th clause.
For example, following MAX E3SAT was given.
- $x_1 \lor x_2 \lor x_3$
- $\overline{x_2} \lor x_4 \lor x_5$
Then, following is corresponding MAX 2SAT problem.
- $x_1$
- $x_2$
- $x_3$
- $\overline{x_1}\lor\overline{x_2}$
- $\overline{x_2}\lor\overline{x_3}$
- $\overline{x_1}\lor\overline{x_3}$
- $y_1$
- $x_1\lor\overline{y_1}$
- $x_2\lor\overline{y_1}$
- $x_3\lor\overline{y_1}$
- $\overline{x_2}$
- $x_4$
- $x_5$
- $x_2\lor\overline{x_4}$
- $\overline{x_4}\lor\overline{x_5}$
- $x_2\lor\overline{x_5}$
- $y_2$
- $\overline{x_2}\lor\overline{y_2}$
- $x_4\lor\overline{y_2}$
- $x_5\lor\overline{y_2}$
Notice that if we make it so then, it shares the optimal solution because MAX 2SAT problem can satisfies 7 of clauses iff corresponding MAX E3SAT problem’s clause satisfies and MAX 2SAT problem can satisfies 6 of clauses otherwise which is less than 7. For example, if $x_1$ is true and $x_4$ is true then, we can set some $y_1$ and $y_2$ to 14 of 20 becomes true.
Now, run the $\alpha$-approximation algorithm for MAX 2SAT on this instance.
Let’s defnine some terminologies.
- $k^{\star}$ be the number of satisfing clauses of MAX E3SAT instance from the optimal solution.
- $\overline{k}$ be the number of satisfing clauses of MAX E3SAT instance from the $\alpha$-approximation algorithm’s output of MAX 2SAT problem.
Notice that we may have some auxiliary variables $y$ but we will just ignore it for $\overline{k}$.
Then, MAX 2SAT instance’s optimal soltuion satisfies $7k^{\star}$ $+$ $6(m - k^{\star})$ clauses. Which means, $\alpha(7k^{\star}$ $+$ $6(m - k^{\star}))$ $\le$ $7\overline{k}$ $+$ $6(m - \overline{k})$. Nocie that $0$ $<$ $\alpha$ $\le$ $1$ because this is maximization problem.
As a result, following inequality is true.
$\alpha(7k^{\star}$ $+$ $6(m - k^{\star}))$ $\le$ $7\overline{k}$ $+$ $6(m - \overline{k})$ $\leftrightarrow$ $\alpha(k^{\star}$ $+$ $6m)$ $\le$ $\overline{k}$ $+$ $6m$ $\leftrightarrow$ $\alpha k^{\star}$ $+$ $\alpha 6m$ $\le$ $\overline{k}$ $+$ $6m$ $\leftrightarrow$ $\alpha k^{\star}$ $+$ $\alpha 6m$ $-$ $6m$ $\le$ $\overline{k}$ $\leftrightarrow$ $\alpha k^{\star}$ $+$ $6(\alpha - 1)m$ $\le$ $\overline{k}$ $\leftrightarrow$ $\alpha k^{\star}$ $-$ $6(1 - \alpha)m$ $\le$ $\overline{k}$.
Now, we already have $\frac{7}{8}$-approximation algorithm. Therefore, $k^{\star}$ $\ge$ $\frac{7}{8}m$ and $\frac{8}{7}k^{\star}$ $\ge$ $m$.
As a result, $\overline{k}$ $\ge$ $\alpha k^{\star}$ $-$ $6(1 - \alpha)m$ $\ge$ $\alpha k^{\star}$ $-$ $6(1 - \alpha)\frac{8}{7}k^{\star}$ $=$ $(\alpha - 6(1 - \alpha)\frac{8}{7})k^{\star}$ $=$ $(\frac{55}{7}\alpha - \frac{48}{7})k^{\star}$.
Notice that $m$ $\le$ $\frac{8}{7}k^{\star}$ $\leftrightarrow$ $-$ $\frac{8}{7}k^{\star}$ $\le$ $-$ $m$ $\leftrightarrow$ $-$ $6(1 - \alpha)\frac{8}{7}k^{\star}$ $\le$ $-$ $6(1 - \alpha)m$.
If there is $\alpha > \frac{433}{440}$, $\overline{k}$ $\ge$ $(\frac{55}{7}\alpha - \frac{48}{7})k^{\star}$ $>$ $(\frac{55}{7}\frac{433}{440} - \frac{48}{7})k^{\star}$ $=$ $(\frac{7}{8})k^{\star}$.
Now, we show that such $\alpha$-approximation for MAX 2SAT can be used to give $(\frac{7}{8} + \epsilon)$-approximation algorithm for MAX-E3SAT problem for some constant $\epsilon > 0$ and $\alpha > \frac{433}{440}$. Which is a contradiction. Therefore, there is no such an approximation algorithm.