MaxE3SAT to Max2SAT (Linear Reduction)

Definition

MaxE3SAT to Max2SAT

There is a linear reduction from MaxE3SAT to Max2SAT with constants

$$\alpha =\frac{55}{7},\beta =1.$$

It replaces each source clause with ten clauses and one fresh auxiliary variable. The target optimum grows by a fixed baseline of six satisfied clauses per source clause, while the backward solution conversion does not increase absolute error.

Construction

Let $F$ have variables $X$ and clauses $C_1,\dots ,C_m$, each containing three literals on distinct variables. We construct a formula $F^{\prime }$ whose clauses have at most two literals. This construction transforms one Boolean formula into another. Here $y_j$ is a new Boolean variable in the target formula.

Replace one clause by ten clauses

For $C_j=(a\vee b\vee c)$, where $a,b,c$ denote literals, introduce a fresh Boolean variable $y_j$ that does not occur in $F$. The index $j$ identifies its group: $C_1$ gets $y_1$, $C_2$ gets $y_2$, and so on. A source assignment specifies only the variables in $X$; a target assignment must also choose the values of the new variables.

Replace $C_j$ by the following ten clauses:

Group	Clauses	What satisfies them?
Three original unit clauses	$(a),(b),(c)$	Each true original literal contributes one.
Three complemented pairs	$(\neg a\vee \neg b),(\neg a\vee \neg c),(\neg b\vee \neg c)$	A pair fails only if both original literals are true.
One auxiliary unit clause	$(y_j)$	Setting $y_j=1$ contributes one.
Three auxiliary pairs	$(a\vee \neg y_j),(b\vee \neg y_j),(c\vee \neg y_j)$	If $y_j=0$, all three are true; if $y_j=1$, they copy $a,b,c$.

Negation here complements a literal: if $a=\neg x$, then $\neg a=x$. Thus the construction also handles negative source literals.

The variable $y_j$ occurs only in this group. Original variables retain their identities across all groups; a truth assignment cannot choose a different value for the same original variable in different clauses.

Count the contribution of the group

Fix the values of $a,b,c$, and let $t\in \{0,1,2,3\}$ count how many are true. The group score counts satisfied target clauses, not true literals.

First count the six clauses without $y_j$. The three unit clauses $(a),(b),(c)$ contribute $t$: each true original literal satisfies its own unit clause.

The other three clauses are

$$(\neg a\vee \neg b),(\neg a\vee \neg c),(\neg b\vee \neg c).$$

Inspect the first one. An OR is false only when both sides are false. Thus $(\neg a\vee \neg b)$ is false exactly when $a=b=1$. Each of these three clauses therefore fails when its corresponding pair of original literals is both true:

Original pair	Target clause that fails if both are true
$\{a,b\}$	$(\neg a\vee \neg b)$
$\{a,c\}$	$(\neg a\vee \neg c)$
$\{b,c\}$	$(\neg b\vee \neg c)$

We can count the failures directly, without a combinatorial formula:

True original literals	Pairs whose two literals are true	Failed pair clauses	Satisfied pair clauses
None	None	$0$	$3$
Only $a$	None: a pair needs two literals	$0$	$3$
$a,b$	Only $\{a,b\}$	$1$	$2$
$a,b,c$	$\{a,b\},\{a,c\},\{b,c\}$	$3$	$0$

Choosing another single true literal or another two true literals gives the same counts; all three pairs are present. For example, with $(a,b,c)=(1,1,0)$, the three target clauses evaluate to $(0\vee 0)$, $(0\vee 1)$, and $(0\vee 1)$: one is false and two are true.

The notation $\left(\genfrac{}{}{0ex}{}{t}{2}\right)$, read “$t$ choose two”, is just a short name for the number of unordered pairs among the $t$ true literals. “Unordered” means that $\{a,b\}$ and $\{b,a\}$ count as the same pair. For the four possibilities here,

$$\left(\genfrac{}{}{0ex}{}{0}{2}\right)=0,\left(\genfrac{}{}{0ex}{}{1}{2}\right)=0,\left(\genfrac{}{}{0ex}{}{2}{2}\right)=1,\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3.$$

For $t\ge 2$, we can also obtain this count as $t(t-1)/2$: choose a first literal in $t$ ways and a different second literal in $t-1$ ways, then divide by two because each pair was counted in both orders. With fewer than two true literals, there is no pair to choose.

Consequently the satisfied pair clauses contribute

$$\underset{\text{all pair clauses}}{\underbrace{3}}-\underset{\text{one failure per pair of true literals}}{\underbrace{\left(\genfrac{}{}{0ex}{}{t}{2}\right)}}.$$

The four clauses containing $y_j$ give us a choice:

• If $y_j=0$, the unit clause $(y_j)$ is false, but $\neg y_j=1$ makes all three auxiliary pairs true: a contribution of $3$.
• If $y_j=1$, the unit clause $(y_j)$ is true, while the auxiliary pairs have the truth values of $a,b,c$: a contribution of $1+t$.

The group scores are therefore

$$\begin{array}{rl}S(t,0)& =\underset{\text{original units}}{\underbrace{t}}+\underset{\text{complemented pairs}}{\underbrace{3-\left(\genfrac{}{}{0ex}{}{t}{2}\right)}}+\underset{\text{auxiliary unit}}{\underbrace{0}}+\underset{\text{auxiliary pairs}}{\underbrace{3}},\\ S(t,1)& =t+\left(3-\left(\genfrac{}{}{0ex}{}{t}{2}\right)\right)+1+t.\end{array}$$

True original literals $t$	Original clause true?	Score if $y_j=0$	Score if $y_j=1$	Best score
$0$	No	$6$	$4$	$6$
$1$	Yes	$7$	$6$	$7$
$2$	Yes	$7$	$7$	$7$
$3$	Yes	$6$	$7$	$7$

Compare the two score columns and keep the better value of $y_j$; either value is suitable in a tie. The best score is exactly
$\max \{S(t,0),S(t,1)\}=6+1[C_j\text{ true}].$
Thus every satisfied source clause can contribute seven target points, regardless of whether one, two, or three of its literals are true. An unsatisfied source clause can contribute only six.

The variable $y_j$ is therefore a scoring choice, not an indicator that $C_j$ is satisfied. For example, when only $a$ is true, $C_j$ is satisfied but the best choice is $y_j=0$. Its role is determined by the clauses above; there is no separate equation defining it from $a,b,c$.

Assemble the target instance

Apply the replacement separately to every source clause. The resulting formula $F^{\prime }$ has variables $X\cup \{y_1,\dots ,y_m\}$ and $10m$ clause occurrences.

Keep repeated clauses as separate occurrences: the objective counts them separately. All target clauses have length one or two, so $F^{\prime }$ is a Max2SAT instance.

Converting Solutions and Optima

Write $O=\mathrm{OPT}(F)$ and $O^{\prime }=\mathrm{OPT}(F^{\prime })$.

The target optimum is $6m+O$

Extend a source assignment

Suppose a source assignment $\sigma$ satisfies $s$ clauses. Construct a target assignment $\tau$ by retaining $\tau (x)=\sigma (x)$ for every $x\in X$. For each group, count the satisfied target clauses with $y_j=0$ and with $y_j=1$, and keep the better choice, as in the table above.

Each $y_j$ occurs only in its own group, so these choices cannot interfere. Two local counts per group suffice; we do not search over all $2^m$ auxiliary assignments or change the original assignment $\sigma$.

In the picture, $X=\{x_1,x_2,x_3\}$ and $\sigma (x_1)=\sigma (x_2)=\sigma (x_3)=1$. The first two source clauses are true and the third is false, so $m=3$ and $s=2$. The local choices are:

Fixed literal values in the source clause	Group score with $y_j=0$	Group score with $y_j=1$	Value to keep
$C_1$: $(1,1,1)$	$6$	$7$	$y_1=1$
$C_2$: $(1,0,0)$	$7$	$6$	$y_2=0$
$C_3$: $(0,0,0)$	$6$	$4$	$y_3=0$

The resulting target assignment satisfies

$$\underset{\text{satisfied source clauses}}{\underbrace{7s}}+\underset{\text{unsatisfied source clauses}}{\underbrace{6(m-s)}}=6m+s$$

clauses. Extending an optimal source assignment gives $O^{\prime }\ge 6m+O$.

Restrict any target assignment

Given any target assignment $\tau$, discard the auxiliary values and retain $\sigma =\tau {|}_X$. Let $s$ be the number of source clauses satisfied by $\sigma$, and let $v^{\prime }$ be the target value of $\tau$.

Each group contributes at most $6$ or $7$, according to whether its source clause is false or true. Hence

$$v^{\prime }\le 6m+s\le 6m+O.$$

This holds for an optimal target assignment too, so $O^{\prime }\le 6m+O$. Combining the two bounds yields $O^{\prime }=6m+O$.

An arbitrary target assignment need not have value $6m+s$: the table includes scores $4$ and $6$ even when a better auxiliary choice exists. We can normalise the assignment by changing only the $y_j$, increasing its value to $6m+s$. The backward conversion itself needs only the restriction $\tau {|}_X$; the inequality above already covers unnormalised assignments.

The Two L-Reduction Bounds

Bound the target optimum: $\alpha =55/7$

A uniformly random source assignment satisfies each three-variable clause with probability $7/8$. Its expected value is $7m/8$, so some source assignment has at least that value. Consequently,

$$O\ge \frac{7}{8}m,m\le \frac{8}{7}O.$$

Substitute this bound on $m$ into the target optimum:

$$O^{\prime }=6m+O\le 6\cdot \frac{8}{7}O+O=\frac{55}{7}O.$$

This controls the added baseline $6m$ relative to the source optimum.

Bound the error after restriction: $\beta =1$

For every target assignment $\tau$ of value $v^{\prime }$, its restricted source assignment has value $s$ with $v^{\prime }\le 6m+s$. Rearranging gives

$$\begin{array}{rl}{O}^{\prime }-v^{\prime }& =6m+O-v^{\prime }\\ & \ge 6m+O-(6m+s)\\ & =O-s.\end{array}$$

Both errors are non-negative because these are maximisation problems. Thus

$$|O-s|\le |O^{\prime }-v^{\prime }|.$$

Restriction does not increase absolute error. After normalising the auxiliary values, the two errors are exactly equal.

Transferring Inapproximability

The aim is to show that a sufficiently good Max2SAT approximation would give a MaxE3SAT approximation that is known to be impossible unless $P=NP$. The following summary is enough to follow the argument without reconstructing the ten-clause gadget.

What we need from the construction

Start with a MaxE3SAT formula $F$ containing $m$ clauses. The reduction builds a Max2SAT formula $F^{\prime }$ in polynomial time. Convert a target assignment back to a source assignment by discarding the auxiliary-variable values and retaining the original-variable values.

Symbol	Meaning
$O=\mathrm{OPT}(F)$	Largest number of source clauses any assignment can satisfy
$O^{\prime }=\mathrm{OPT}(F^{\prime })$	Largest number of target clauses any assignment can satisfy
$v^{\prime }$	Number of target clauses satisfied by the returned target assignment
$s$	Number of source clauses satisfied after converting that assignment back
$\rho$	Hypothetical target approximation ratio: $v^{\prime }\ge \rho O^{\prime }$ on every instance, with $0\le \rho \le 1$

The construction above establishes two bounds:

The target optimum is not too large

The gadget gives $O^{\prime }=6m+O$. Some source assignment satisfies at least $7m/8$ clauses, so $m\le 8O/7$. Hence
$O^{\prime }=6m+O\le \frac{55}{7}O.$
We need only the final bound: the target optimum is at most $55/7$ times the source optimum.

Converting back does not increase the missing value

For every target assignment, even one with poor auxiliary choices,

$$\underset{\text{source shortfall from optimality}}{\underbrace{O-s}}\le \underset{\text{target shortfall from optimality}}{\underbrace{O^{\prime }-v^{\prime }}}.$$

These are shortfalls from the respective optima, not counts of all unsatisfied clauses. This bound is why a good target solution gives a good source solution.

Neither the reduction nor the approximation algorithm needs to know $O$ or $O^{\prime }$. They are reference values used in the proof.

The scales depict the hypothetical case $\rho >433/440$. The source error bound stays below $1/8$, so converting the target algorithm would guarantee more than $7/8$ of the source optimum on every instance—not merely on one lucky assignment.

What a target approximation would give us

Suppose a polynomial-time Max2SAT algorithm guarantees ratio $\rho$. We could approximate a source instance by constructing $F^{\prime }$, running that algorithm, and discarding the auxiliary values of its returned assignment. All three operations take polynomial time.

First express the target guarantee as a bound on the missing value:

$$v^{\prime }\ge \rho O^{\prime }⟹O^{\prime }-v^{\prime }\le (1-\rho )O^{\prime }.$$

For example, $\rho =0.99$ permits a shortfall of at most $1\%$ of the target optimum. Apply the two construction bounds:

$$\begin{array}{rlrl}O-s& \le O^{\prime }-v^{\prime }& & \text{conversion does not increase the shortfall}\\ & \le (1-\rho )O^{\prime }& & \text{target approximation guarantee}\\ & \le \frac{55}{7}(1-\rho )O& & \text{bound the target optimum using the source optimum}.\end{array}$$

Subtract this allowed shortfall from the source optimum $O$:

$$\begin{array}{rl}s& \ge O-\frac{55}{7}(1-\rho )O\\ & =\underset{\text{guaranteed source approximation ratio}}{\underbrace{\left(1-\frac{55}{7}(1-\rho )\right)}}O.\end{array}$$

For $\rho =0.99$, the source ratio is approximately $0.9214$. The target’s $1\%$ allowed relative shortfall has become at most $7.86\%$ on the source side.

When this contradicts known hardness

The separate inapproximability theorem for MaxE3SAT says: unless $P=NP$, no polynomial-time algorithm guarantees a fixed ratio strictly greater than $7/8=0.875$ on every MaxE3SAT instance. This is the hardness result we start from; the gadget itself does not prove it.

Our hypothetical target algorithm would contradict that theorem whenever its induced source ratio exceeds $7/8$:

$$\begin{array}{rl}1-\frac{55}{7}(1-\rho )& >\frac{7}{8},\\ \frac{55}{7}(1-\rho )& <\frac{1}{8},\\ 1-\rho & <\frac{7}{440},\\ \rho & >\frac{433}{440}\approx \mathrm{0.9841.}\end{array}$$

Therefore, unless $P=NP$, Max2SAT has no polynomial-time approximation algorithm with a fixed ratio greater than $433/440$. In particular, a $0.99$-approximation would be too good: it would yield the forbidden source ratio $0.9214>0.875$.

This applies inapproximability transfer under L-reductions with $\alpha =55/7$ and $\beta =1$. It is the bound obtained by this reduction, not necessarily the strongest known Max2SAT bound. The boundary ratio $433/440$ itself is not excluded: it yields exactly $7/8$ for the source, which the stated hardness theorem permits.

Running Time

The instance conversion writes ten clauses and introduces one variable per source clause, producing $n+m$ variables and $10m$ clauses. It uses $O(n+m)$ operations on variable identifiers; the bit encoding also has polynomial size. Restricting a target assignment takes $O(n)$ operations, and optional auxiliary normalisation takes $O(m)$ more.

Both conversions are polynomial-time. Neither conversion solves the target optimisation problem.

Example

A poor auxiliary choice is not a poor source assignment

Take the single source clause $C=(x_1\vee x_2\vee x_3)$ and set $x_1=x_2=x_3=1$. The source clause is satisfied, so the source value is $1=O$.

With $y=0$, the target group has $3$ true original units, $0$ true complemented pairs, $0$ true auxiliary units, and $3$ true auxiliary pairs: its value is $6$. Since $O^{\prime }=7$, its target error is $1$.

Restriction already gives an optimal source solution, with error $0\le 1$. Changing only $y$ to $1$ raises the target score to $7$ and makes both errors zero. This is why the L-reduction requires an error inequality for every target assignment, not equality before normalisation.