MAXEkSAT is a problem in computational complexity theory that is a maximization version of the Boolean satisfiability problem3SAT. In MAXEkSAT, each clause has exactly k literals, each with distinct variables, and is in conjunctive normal form. These are called k-CNF formulas. The problem is to determine the maximum number of clauses that can be satisfied by a truth assignment to the variables in the clauses. We say that an algorithm A provides an α-approximation to MAXEkSAT if, for some fixed positive αless than or equal to 1, and every kCNF formula φ, A can find a truth assignment to the variables of φ that will satisfy at least an α-fraction of the maximum number of satisfiable clauses of φ. Because the NP-hardk-SAT problem is equivalent to determining if the corresponding MAXEkSAT instance has a valueequal to the number of clauses, MAXEkSAT must also be NP-hard, meaning that there is no polynomial time algorithm unless P=NP. A natural next question, then, is that of finding approximate solutions: what's the largest real numberα < 1 such that some explicit P algorithm always finds a solution of size α·OPT, where OPT is the maximizing assignment.
Approximation Algorithm
There is a simple randomized polynomial-time algorithm that provides a -approximation to MAXEkSAT: independently set each variable to true with probability, otherwise set it to false. Any given clause c is unsatisfied only if all of its k constituent literals evaluates to false. Because each literal within a clause has a chance of evaluating to true independently of any of the truth value of any of the other literals, the probability that they are all false is. Thus, the probability that c is indeed satisfied is, so the indicator variable has expectation. The sum of all of the indicator variables over all clauses is, so by linearity of expectation we satisfy a fraction of the clauses in expectation. Because the optimal solution can't satisfy more than all of the clauses, we have that, so the algorithm finds a approximation to the true optimal solution in expectation. Despite its high expectation, this algorithm may occasionally stumble upon solutions of value lower than the expectation we computed above. However, over a large number of trials, the average fraction of satisfied clauses will tend towards. This implies two things:
There must exist an assignment satisfying at least a fraction of the clauses. If there weren't, we could never attain a value this large on average over a large number of trials.
If we run the algorithm a large number of times, at least half of the trials will satisfy some fraction of the clauses. This is because any smaller fraction would bring down the average enough that the algorithm must occasionally satisfy more than 100% of the clauses to get back to its expectation of, which cannot happen. Extending this using Markov's inequality, at least some -fraction of the trials will satisfy at least an -fraction of the clauses. Therefore, for any positive, it takes only a polynomial number of random trials until we expect to find an assignment satisfying at least an fraction of the clauses.
A more robust analysis shows that we will, in fact, satisfy at least a -fraction of the clauses a constant fraction of the time, with no loss of.
Derandomization
While the above algorithm is efficient, it's not obvious how to remove its dependence on randomness. Trying out all possible random assignments is equivalent to the naive brute force approach, so may take exponential time. One clever way to derandomize the above in polynomial time relies on work inerror correcting codes, satisfying a fraction of the clauses in time polynomial in the input size. We need one definition and two facts to find the algorithm.
Definition
is an ℓ-wise independent source if, for a uniformly chosen random ∈ S, x1, x2, ..., xn are ℓ-wise independent random variables.
Fact 1
Note that such an assignment can be found among elements of any ℓ-wise independent source over n binary variables. This is easier to see once you realize that an ℓ-wise independent source is really just any set of binary vectors over n with the property that all restrictions of those vectors to ℓ co-ordinates must present the 2ℓ possible binary combinations an equal number of times.
Fact 2
Recall that BCH2,m,d is an linear code. There exists an ℓ-wise independent source of size, namely the dual of a BCH2,log n,ℓ+1 code, which is a linear code. Since every BCH code can be presented as a polynomial-time computable restriction of a related Reed Solomon code, which itself is strongly explicit, there is a polynomial-time algorithm for finding such an assignment to the xi's. The proof of fact 2 can be found at Dual of BCH is an independent source.
The algorithm works by generating BCH2,log n,ℓ+1, computing its dual and treating each element of that source as a truth assignment to the n variables in φ. At least one of them will satisfy at least 1 − 2−ℓ of the clauses of φ, whenever φ is in kCNF form, k = ℓ.
Related problems
There are many problems related to the satisfiability of conjunctive normal form Boolean formulas.
* The partial maximum satisfiability problem asks for the maximum number of clauses which can be satisfied by any assignment of a given subset of clauses. The rest of the clauses must be satisfied.
* The soft satisfiability problem, given a set of SAT problems, asks for the maximum number of sets which can be satisfied by any assignment.
* The minimum satisfiability problem.
The MAX-SAT problem can be extended to the case where the variables of the constraint satisfaction problem belong the set of reals. The problem amounts to finding the smallest q such that the q-relaxed intersection of the constraints is not empty.
