MAXEkSAT

There is a simple randomized polynomial-time algorithm that provides a ${\displaystyle \textstyle \left(1-{\frac {1}{2^{k}}}\right)}$-approximation to MAXEkSAT: independently set each variable to true with probability 1/2, 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 1⁄2 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 ${\displaystyle \textstyle ({\frac {1}{2}})^{k}={\frac {1}{2^{k}}}}$. Thus, the probability that c is indeed satisfied is ${\displaystyle \textstyle 1-{\frac {1}{2^{k}}}}$, so the indicator variable ${\displaystyle \textstyle 1_{c}}$ (that is 1 if c is true and 0 otherwise) has expectation ${\displaystyle \textstyle 1-{\frac {1}{2^{k}}}}$. The sum of all of the indicator variables over all ${\displaystyle \textstyle |C|}$ clauses is ${\displaystyle (\textstyle 1-{\frac {1}{2^{k}}})|C|}$, so by linearity of expectation we satisfy a ${\displaystyle \textstyle \left(1-{\frac {1}{2^{k}}}\right)}$ fraction of the clauses in expectation. Because the optimal solution can't satisfy more than all ${\displaystyle \textstyle |C|}$ of the clauses, we have that ${\displaystyle {\textit {ALG}}=\left(1-{\frac {1}{2^{k}}}\right)\cdot |C|>\left(1-{\frac {1}{2^{k}}}\right)\cdot {\textit {OPT}}}$, so the algorithm finds a ${\displaystyle \textstyle \geq \left(1-{\frac {1}{2^{k}}}\right)}$ 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 ${\displaystyle \textstyle \left(1-{\frac {1}{2^{k}}}\right)}$. This implies two things:

1. There must exist an assignment satisfying at least a ${\displaystyle \textstyle \left(1-{\frac {1}{2^{k}}}\right)}$ fraction of the clauses. If there weren't, we could never attain a value this large on average over a large number of trials.
2. If we run the algorithm a large number of times, at least half of the trials (in expectation) will satisfy some ${\displaystyle \textstyle (1-{\frac {2}{2^{k}}})}$ 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 ${\displaystyle \textstyle \left(1-{\frac {2}{2^{k}}}\right)}$, which cannot happen. Extending this using Markov's inequality, at least some ${\displaystyle \textstyle 1-\left({\frac {1}{1+2^{k}\epsilon }}\right)}$-fraction of the trials (in expectation) will satisfy at least an ${\displaystyle \textstyle \left(1-{\frac {1}{2^{k}}}-\epsilon \right)}$-fraction of the clauses. Therefore, for any positive ${\displaystyle \textstyle \epsilon }$, it takes only a polynomial number of random trials until we expect to find an assignment satisfying at least an ${\displaystyle \textstyle \left(1-{\frac {1}{2^{k}}}-\epsilon \right)}$ fraction of the clauses.

A more robust analysis (such as that in [1]) shows that we will, in fact, satisfy at least a ${\displaystyle \textstyle \left(1-{\frac {1}{2^{k}}}\right)}$-fraction of the clauses a constant fraction of the time (depending only on k), with no loss of ${\displaystyle \textstyle \epsilon }$.

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 in error correcting codes, satisfying a ${\displaystyle \textstyle \left(1-{\frac {1}{2^{k}}}\right)}$ fraction of the clauses in time polynomial in the input size (although the exponent depends on k).

We need one definition and two facts to find the algorithm.

There are many problems related to the satisfiability of conjunctive normal form Boolean formulas.

• Decision problems:
  • 2SAT
  • 3SAT
• Optimization problems, where the goal is to maximize the number of clauses satisfied:
  • MAX-SAT, and the corresponded weighted version Weighted MAX-SAT
  • MAX-kSAT, where each clause has exactly k variables:
    • MAX-2SAT
    • MAX-3SAT
    • MAXEkSAT
  • The partial maximum satisfiability problem (PMAX-SAT) 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 (soft-SAT), given a set of SAT problems, asks for the maximum number of sets which can be satisfied by any assignment.[2]
  • 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.[3]

• Coding Theory notes at MIT