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:
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 (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 ∈ P C P ( O ( log ( n ) ) , O ( 1 ) ) {\displaystyle 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
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 Ri ∈ V, we obtain poly(x) strings since the length of each string r ( x ) = O ( log | x | ) {\displaystyle r(x)=O(\log |x|)} . For each Ri V chooses q positions i1,...,iq and a Boolean function fR: {0,1}q->{0,1} and accepts if and only if fR(π(i1,...,iq)). Here π refers to the proof obtained from the Oracle. 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.
For every R, add clauses representing fR(xi1,...,xiq) using 2q SAT clauses. Clauses of length q are converted to length 3 by adding new (auxiliary) variables e.g. x2 ∨ x10 ∨ x11 ∨ x12 = ( x2 ∨ x10 ∨ yR) ∧ ( yR ∨ x11 ∨ x12). This requires a maximum of q2q 3-SAT clauses. If z ∈ L then there is a proof π such that Vπ (z) accepts for every Ri. All clauses are satisfied if xi = π(i) and the auxiliary variables are added correctly. If input z ∉ L then For every assignment to x1,...,xl and yR's, the corresponding proof π(i) = xi causes the Verifier to reject for half of all R ∈ {0,1}r(|z|). For each R, one clause representing fR fails. Therefore, a fraction 1 2 1 q 2 q {\displaystyle {\frac {1}{2}}{\frac {1}{q2^{q}}}} 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 O ( log ( n ) ) {\displaystyle 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
z ∈ L ⟹ ∃ π P r [ V π ( z ) = 1 ] ≥ 1 − ϵ {\displaystyle z\in L\implies \exists \pi Pr[V^{\pi }(z)=1]\geq 1-\epsilon }
z ∉ L ⟹ ∀ π P r [ V π ( z ) = 1 ] ≤ 1 2 + ϵ {\displaystyle z\not \in L\implies \forall \pi Pr[V^{\pi }(z)=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
… excerpt ends here. Continue reading the full article.
