Maximum Exact-3-SAT Optimisation Problem

Definition

Maximum Exact-3-SAT Optimisation Problem

Instance: A CNF formula $F=C_1\wedge \cdots \wedge C_m$, where every clause contains exactly three literals on three distinct variables.

Feasible solutions: All truth assignments $\sigma :\mathrm{Var}(F)\to \{0,1\}$.

Objective: Maximise the number of satisfied clauses:

$${\mathrm{val}}_F(\sigma )=\sum _{j=1}^{m}1[\sigma \models C_j],\mathrm{OPT}(F)=\underset{\sigma }{\max }{\mathrm{val}}_F(\sigma ).$$

Here $1[P]$ is $1$ if $P$ holds and $0$ otherwise. An assignment is optimal exactly when its value equals $\mathrm{OPT}(F)$. Each clause occurrence counts separately.

“Exact-3” specifies clause length, not a requirement that exactly one literal be true. This is a special case of Max3SAT.

The Seven-Eighths Bound

Under independent uniform variable choices, each clause is false with probability $(1/2{)}^3=1/8$. Summing clause satisfaction probabilities gives

$$\mathbb{E}[{\mathrm{val}}_F(\sigma )]=\frac{7}{8}m,\mathrm{OPT}(F)\ge \frac{7}{8}m.$$

The second inequality holds because the maximum value is at least the average value. This also gives a randomised $7/8$-approximation, since $\mathrm{OPT}(F)\le m$; conditional expectation can derandomise it.

A standard inapproximability theorem states that, for every fixed $\delta >0$, no polynomial-time algorithm guarantees a value at least $(7/8+\delta )\mathrm{OPT}(F)$ on every instance unless $P=NP$. This is a separate hardness theorem, not a consequence of the random-assignment calculation.

The linear reduction to Max2SAT uses this theorem as its starting hardness result.