MAXEkSAT

MAXEkSAT is a problem in computational complexity theory that is a maximization version of the Boolean satisfiability problem 3SAT. 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-hard k-SAT problem (for k ≥ 3) is equivalent to determining if the corresponding MAXEkSAT instance has a value equal 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 (complexity) algorithm always finds a solution of size α·OPT, where OPT is the (potentially hard to find) maximizing assignment. While the algorithm is efficient, it's not obvious how to remove its dependence on randomness. There are problems related to the satisfiability of conjunctive normal form Boolean formulas.

Approximation Algorithm

There is a simple randomized polynomial-time algorithm that provides a

(

1

−

1

2

k

)

{\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

(

1

2

)

k

=

1

2

k

{\displaystyle \textstyle ({\frac {1}{2}})^{k}={\frac {1}{2^{k}}}}

.