Maximum Exact-3-SAT Optimisation Problem

Definition

Maximum Exact-3-SAT Optimisation Problem

Instance: A CNF formula , where every clause contains exactly three literals on three distinct variables.

Feasible solutions: All truth assignments .

Objective: Maximise the number of satisfied clauses:

Here is if holds and otherwise. An assignment is optimal exactly when its value equals . 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 . Summing clause satisfaction probabilities gives

The second inequality holds because the maximum value is at least the average value. This also gives a randomised -approximation, since ; conditional expectation can derandomise it.

A standard inapproximability theorem states that, for every fixed , no polynomial-time algorithm guarantees a value at least on every instance unless . 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.