MAX-3SAT is a problem in the computational complexity subfield of computer science. It generalises the Boolean satisfiability problem (SAT) which is a decision problem considered in complexity theory. It is defined as: Given a 3-CNF formula Φ (i.e. with at most 3 variables per clause), find an assignment that satisfies the largest number of clauses. MAX-3SAT is a canonical complete problem for the complexity class MAXSNP (shown complete in Papadimitriou pg. 314).

Approximability

The decision version of MAX-3SAT is NP-complete. Therefore, a polynomial-time solution can only be achieved if P = NP. An approximation within a factor of 2 can be achieved with this simple algorithm, however: The Karloff-Zwick algorithm runs in polynomial-time and satisfies ≥ 7/8 of the clauses. While this algorithm is randomized, it can be derandomized using, e.g., the techniques from to yield a deterministic (polynomial-time) algorithm with the same approximation guarantees.

Theorem 1 (inapproximability)

The PCP theorem implies that there exists an ε > 0 such that (1-ε)-approximation of MAX-3SAT is NP-hard. Proof: Any NP-complete problem L \in \mathsf{PCP}(O(\log (n)), O(1)) by the PCP theorem. For x ∈ L, a 3-CNF formula Ψx is constructed so that The Verifier V reads all required bits at once i.e. makes non-adaptive queries. This is valid because the number of queries remains constant. Next we try to find a Boolean formula to simulate this. We introduce Boolean variables x1,...,xl, where l is the length of the proof. To demonstrate that the Verifier runs in Probabilistic polynomial-time, we need a correspondence between the number of satisfiable clauses and the probability the Verifier accepts. It can be concluded that if this holds for every NP-complete problem then the PCP theorem must be true.

Theorem 2

Håstad demonstrates a tighter result than Theorem 1 i.e. the best known value for ε. He constructs a PCP Verifier for 3-SAT that reads only 3 bits from the Proof. For every ε > 0, there is a PCP-verifier M for 3-SAT that reads a random string r of length O(\log(n)) and computes query positions ir, jr, kr in the proof π and a bit br. It accepts if and only if 'π(ir) ⊕ π(jr) ⊕ π(kr) = br.'' The Verifier has completeness (1−ε) and soundness 1/2 + ε (refer to PCP (complexity)). The Verifier satisfies If the first of these two equations were equated to "=1" as usual, one could find a proof π by solving a system of linear equations (see MAX-3LIN-EQN) implying P = NP. This is enough to prove the hardness of approximation ratio

Related problems

MAX-3SAT(B) is the restricted special case of MAX-3SAT where every variable occurs in at most B clauses. Before the PCP theorem was proven, Papadimitriou and Yannakakis showed that for some fixed constant B, this problem is MAX SNP-hard. Consequently, with the PCP theorem, it is also APX-hard. This is useful because MAX-3SAT(B) can often be used to obtain a PTAS-preserving reduction in a way that MAX-3SAT cannot. Proofs for explicit values of B include: all B ≥ 13, and all B ≥ 3 (which is best possible). Moreover, although the decision problem 2SAT is solvable in polynomial time, MAX-2SAT(3) is also APX-hard. The best possible approximation ratio for MAX-3SAT(B), as a function of B, is at least and at most, unless NP=RP. Some explicit bounds on the approximability constants for certain values of B are known. Berman, Karpinski and Scott proved that for the "critical" instances of MAX-3SAT in which each literal occurs exactly twice, and each clause is exactly of size 3, the problem is approximation hard for some constant factor. MAX-EkSAT is a parameterized version of MAX-3SAT where every clause has exactly k literals, for k ≥ 3. It can be efficiently approximated with approximation ratio using ideas from coding theory. It has been proved that random instances of MAX-3SAT can be approximated to within factor 8⁄9.