MAX-3SAT

MAX-3SAT is a problem in the computational complexity subfield of computer science. It generalises the Boolean satisfiability problem which is a decision problem considered in complexity theory. It is defined as:
Given a 3-CNF formula Φ, find an assignment that satisfies the largest number of clauses.
MAX-3SAT is a canonical complete problem for the complexity class MAXSNP.

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:

Output the solution in which most clauses are satisfied, when either all variables = TRUE or all variables = FALSE.
Every clause is satisfied by one of the two solutions, therefore one solution satisfies at least half of the clauses.

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 algorithm with the same approximation guarantees.

Theorem 1 (inapproximability)

The PCP theorem implies that there exists an ε > 0 such that -approximation of MAX-3SAT is NP-hard.
Proof:
Any NP-complete problem by the PCP theorem. For x ∈ L, a 3-CNF formula Ψ_x is constructed so that

x ∈ L ⇒ Ψ_x is satisfiable
x ∉ L ⇒ no more than m clauses of Ψ_x are satisfiable.

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.

Let q be the number of queries.
Enumerating all random strings R_i ∈ V, we obtain poly strings since the length of each string.
For each R_i
* V chooses q positions i₁,...,i_q and a Boolean function f_R: ^q-> and accepts if and only if f_R. Here π refers to the proof obtained from the Oracle.

Next we try to find a Boolean formula to simulate this. We introduce Boolean variables x₁,...,x_l, 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.

For every R, add clauses representing f_R using 2^q SAT clauses. Clauses of length q are converted to length 3 by adding new variables e.g. x₂ ∨ x₁₀ ∨ x₁₁ ∨ x₁₂ = ∧. This requires a maximum of q2^q 3-SAT clauses.
If z ∈ L then
* there is a proof π such that V^π accepts for every R_i.
* All clauses are satisfied if x_i = π and the auxiliary variables are added correctly.
If input z ∉ L then
* For every assignment to x₁,...,x_l and y_R's, the corresponding proof π = x_i causes the Verifier to reject for half of all R ∈ ^r.
** For each R, one clause representing f_R fails.
** Therefore, a fraction of clauses fails.

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 and computes query positions i_r, j_r, k_r in the proof π and a bit b_r. It accepts if and only if π ⊕ π ⊕ π = b_r.

The Verifier has completeness and soundness 1/2 + ε. 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 implying P = NP.

If z ∈ L, a fraction ≥ of clauses are satisfied.
If z ∉ L, then for a fraction of R, 1/4 clauses are contradicted.

This is enough to prove the hardness of approximation ratio

Related problems

MAX-3SAT 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 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.
Moreover, although the decision problem 2SAT is solvable in polynomial time, MAX-2SAT is also APX-hard.
The best possible approximation ratio for MAX-3SAT, 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 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.