# 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

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\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 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$_1$,...,i$_q$ and a Boolean function f$_R$: {0,1}$^q$->{0,1} and accepts if and only if f$_R$(π(i$_1$,...,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$_1$,...,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$_2$ ∨ x$_{10}$ ∨ x$_{11}$ ∨ x$_{12}$ = ( x$_2$ ∨ x$_{10}$ ∨ y$_R$) ∧ ( y$_R$ ∨ x$_{11}$ ∨ x$_{12}$). 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$_1$,...,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}{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))$⁠ 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 }(z)=1]\geq 1-\epsilon$
    $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
    ${\frac {1-{\frac {1}{4}}({\frac {1}{2}}-\epsilon )}{1-\epsilon }}={\frac {7}{8}}+\epsilon '$

## 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 $7/8+\Omega (1/B)$ and at most $7/8+O(1/{\sqrt {B}})$, 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 $1-(1/2)^{k}$ using ideas from coding theory.
It has been proved that random instances of MAX-3SAT can be approximated to within factor ⁠8/9⁠.