MAX-3SAT

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

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 if and only if "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 correspondence 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) ∧ ( ∨ "x"₁₁ ∨ "x"₁₂). This requires a maximum of "q"2^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 $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 if and only if"

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

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

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

$z\; ot\; in\; L\; implies\; forall\; pi\; Pr\; [V^\{pi\}\; (x)\; =\; 1]\; le\; 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

$frac\{1-frac\{1\}\{4\}(frac\{1\}\{2\}-epsilon)\}\{1-epsilon\}\; =\; frac\{7\}\{8\}\; +\; epsilon\text{'}$

References

[http://www.cs.berkeley.edu/~luca/notes/ Lecture Notes from University of California, Berkeley]