Maximum 3-SAT Optimisation Problem

Definition

Maximum 3-SAT Optimisation Problem

Instance: A CNF formula , where every clause contains at most three literals.

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.

This is the restriction of MaxSAT to clauses of length at most three; unit and two-literal clauses are allowed.

At Most Three versus Exactly Three

MaxE3SAT requires exactly three literals on distinct variables in every clause. It is a special case of Max3SAT, not a different spelling of the same restriction.

Uniform independent random assignment satisfies a three-variable clause with probability , but a unit clause only with probability . Thus the random-assignment guarantee for MaxE3SAT does not apply directly to general Max3SAT.

Example

A mixed-length instance

The formula is a Max3SAT instance but not a MaxE3SAT instance. Setting satisfies all three clauses, so .