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 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: ^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) ∧ ( _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'' ∈ ^{''r''(, ''z'', )}.
*** For each ''R'', one clause representing ''f''_R fails.
*** Therefore, a fraction $\frac \frac$ 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 ''π''(''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 ^ (z) = 1\ge 1 - \epsilon

:z \not \in L \implies \forall \pi Pr ^ (z) = 1\le \frac + \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 = \frac + \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'' ≥ 3Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti Spaccamela, A., and Protasi, M. (1999), Complexity and Approximation. Combinatorial Optimization Problems and their Approximability Properties,
Springer-Verlag, Berlin. Section 8.4. (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)$, 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 $1- (1/2)^$ using ideas from coding theory.

It has been proved that random instances of MAX-3SAT can be approximated to within factor .
W.F.de la Vega and M.Karpinski, 9/8-Approximation Algorithm for Random MAX-3SAT
ECCC TR 02-070 (2002)
RAIRO-Operations Research 41 (2007), pp.95-107]

References

{{reflist}
Lecture Notes from University of California, BerkeleyCoding theory notes at University at Buffalo

Satisfiability problems
NP-hard problems