MAX-E3SAT is the problem of finding a truth assignment that maximizes the number of satisfied clauses, where each clause contains exactly three literals.
MAX-2SAT is the same problem where each clause contains at most two literals.
A $\frac{7}{8}$-approximation algorithm exists for MAX-E3SAT.
Proof. For each variable $x_i$, count how many clauses contain $x_i$ and how many contain $\overline{x_i}$. Setting $x_i$ to whichever value satisfies more clauses ensures at least half of the occurrences are satisfied. Since each clause has three literals, a random assignment satisfies each clause with probability at least $\frac{7}{8}$ (the only bad outcome is all three literals being falsified, with probability $\frac{1}{8}$).
Furthermore, P $=$ NP if there exists a $(\frac{7}{8} + \epsilon)$-approximation algorithm for MAX-E3SAT for any 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 $l_1$, $l_2$, and $l_3$, consider the following ten clauses involving $l_1, l_2, l_3$ and an 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 $l_1 \lor l_2 \lor l_3$ is satisfied, we can choose $y$ so that exactly 7 of the 10 clauses are satisfied, and no more than 7 can be satisfied. If $l_1 \lor l_2 \lor l_3$ is not satisfied, we can choose $y$ so that exactly 6 of the 10 clauses are satisfied, and no more than 6 can be satisfied.
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 |
Consider an instance of MAX E3SAT with $m$ clauses and $n$ variables. We construct a MAX 2SAT instance as follows.
For each $j$-th clause in the MAX E3SAT instance, introduce 10 clauses using the construction above, with a distinct auxiliary variable $y_j$. Set $l_1$, $l_2$, $l_3$ to the literals in the $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.
Define the following terms.
- $k^\star$: the number of satisfied clauses in the optimal MAX E3SAT solution.
- $\overline{k}$: the number of MAX E3SAT clauses satisfied by the solution output by the $\alpha$-approximation algorithm for MAX 2SAT (ignoring auxiliary variables $y_j$).
The optimal MAX 2SAT solution satisfies $7k^\star + 6(m - k^\star)$ clauses. By the $\alpha$-approximation guarantee, $\alpha(7k^\star + 6(m - k^\star)) \le 7\overline{k} + 6(m - \overline{k})$. Note that $0 < \alpha \le 1$ since this is a 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}$.
We have shown that an $\alpha$-approximation for MAX 2SAT with $\alpha > \frac{433}{440}$ yields a $(\frac{7}{8} + \epsilon)$-approximation for MAX-E3SAT for some constant $\epsilon > 0$. This contradicts the inapproximability of MAX-E3SAT beyond $\frac{7}{8}$ unless P $=$ NP. Therefore, no such approximation algorithm exists for MAX 2SAT unless P $=$ NP.