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.
Read more about this topic: MAX-3SAT