Overview

MAX-3SAT is a language in the Computational Complexity subfield of Computer Science. It is a special case of the Boolean satisfiability problem (SAT) which is a decision problem considered in complexity theory. Informally it can be 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.

Approximability

An exact solution of MAX-3SAT is NP-hard. 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.

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 ∈ PCP(O(log (n)), O(1)) 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 (1-ε)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(x) strings since the length of each string r(x) = O(log |x|).
• For each R_i
  • V chooses q positions i₁,...,i_q and a Boolean function f_R: {0,1}^q and accepts iff f_R(π(i₁,...,i_q)). 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 correspondance between the number of satisfiable clauses and the probability the Verifier accepts.

• For every R, add clauses representing f_R(x_i1,...,x_iq) using 2^q SAT clauses. Clauses of length q are converted to length 3 by adding new (auxiliary) variables e.g. x₂ ∨ x₁₀ ∨ x₁₁ ∨ x₁₂ = ( x₂ ∨ x₁₀ ∨ y_R) ∧ ( ${\displaystyle {\bar {y_{R}}}}$ ∨ x₁₁ ∨ x₁₂). This requires a maximum of q2^q 3-SAT clauses.
• If z ∈ L then
  • there is a proof π such that V^π (z) accepts for every R_i.
  • All clauses are satisfied if x_i = π(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 π(i) = x_i causes the Verifier to reject for half of all R ∈ {0,1}^r(|z|).
    • For each R, one clause representing f_R fails.
    • Therefore a fraction ${\displaystyle {\frac {1}{2}}{\frac {1}{q^{2^{q}}}}}$ of clauses fails.

It can be concluded that if this holds for every NP-complete problem then the PCP Theorem must be true.

Related problems

MAX-3SAT(13) is a restricted version of MAX-3SAT where every variable occurs in at most 13 clauses.

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 i_r, j_r, k_r in the proof π and a bit b_r. It accepts iff

π(i_r) ⊕ π(j_r) ⊕ π(k_r) ⊕ = b_r.

The Verifier has completeness (1-ε) and soundness 1/2 + ε (refer to PCP (complexity)). The Verifier satisfies

${\displaystyle z\in L\implies \exists \pi Pr[V^{\pi }(x)=1]\geq 1-\epsilon }$

${\displaystyle z\not \in L\implies \forall \pi Pr[V^{\pi }(x)=1]\leq {\frac {1}{2}}+\epsilon }$ 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.

• If z ∈ L, a fraction ≥ (1- ε) of clauses are satisfied.
• If z ∉ L, then for a (1/2- ε) fraction of R, 1/4 clauses are contradicted.

This is enough to prove the hardness of approximation ratio ${\displaystyle {\frac {1-{\frac {1}{4}}({\frac {1}{2}}-\epsilon )}{1-\epsilon }}={\frac {7}{8}}+\epsilon '}$

References

Luca Trevisan's Lecture Notes

University of California, Berkeley http://www.cs.berkeley.edu/~luca/notes/