QI (G series)

Template:Expert-subject Template:Lead too short 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, with k ≥ 3, and is in conjunctive normal form. These formulas are called kCNF 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 φ.

Note that since 3SAT is NP-hard, and since any 1-approximation algorithm for MAXEkSAT could easily be converted into an algorithm for accepting the language 3SAT, 1-approximation of MAXEkSAT is NP-hard.

A natural next question is how big α can be guaranteed to be for an explicit algorithm that runs in polynomial time (P).

Main idea

A simple result is that there is a simple randomized algorithm that provides a 7/8-approximation to MAXE3SAT which runs in polynomial time: For each i, set variable x_i in formula φ to be true with probability 1/2, and false with probability 1/2.

Proof

In a 3CNF formula, there are three boolean variables; consequently, the number of possible combination of assignments to the three variables is 8. Since there is only one combination of truth assignments to a clause that will render it false, we have a 7/8 probability of stumbling across a valid assignment for any given clause. Thus, the expected fraction of satisfied clauses is 7/8. Because this expectation is over all possible assignments to variables, this guarantees the existence of some assignment that satisfies at least 7/8-fraction of clauses of any 3CNF formula.

Main question

But even if we know that there exists such a satisfying assignment, how would we find one? We could cycle through all 2ⁿ assignments until we found one, but clearly that approach can't be guaranteed to run in polynomial time.

One answer, relying on results in the study of error correcting codes, works for any constant k, providing a polynomial time algorithm for finding such an assignment.

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

Definition

$S\subseteq \{0,1{\}}^n$ is an ℓ-wise independent source if, for a uniformly chosen random (x₁, x₂, ..., x_n) ∈ S, x₁, x₂, ..., x_n 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 {0, 1}ⁿ 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 BCH_2,m,d is an $[n=2^m,n-1-\lceil d-2/2\rceil m,d{]}_2$ linear code.

There exists an ℓ-wise independent source of size $O(n^{\lfloor \ell /2\rfloor })$, namely the dual of a BCH_{2,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 x_i's. The proof of fact 2 can be found at Dual of BCH is an independent source.

To summarize, generate BCH_{2,log n,ℓ+1}, compute its dual, which as a set is an ℓ-wise independent source, and treat each element (codeword) 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 = ℓ.

For ℓ = 3, this derandomizes the initially described algorithm for MAXE3SAT.

Related problems

MAX3SAT is a relaxed version of MAXEkSAT, where each clause can have no more than three literals.

References

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

• Coding Theory notes at University at Buffalo
• Coding Theory notes at MIT