Randomized algorithm for 3SAT

Question

There is a very simple randomized algorithm that, given a 3SAT, produces an assignment satisfying at least 7/8 of the clauses (in expectation): choose a random assignment. A random assignment satisfies each clause with probability 7/8, and so linearity of expectation shows that the expected fraction of clauses satisfied by a random assignment is 7/8.

Can this be done in a deterministic way? If so, why are we interested in the randomized algorithm?

Answer 1

The random assignment algorithm can be derandomized (made deterministic) using the method of conditional expectations.

Let the 3SAT instance consist of clauses $C_1,\ldots,C_m$. During the algorithm we will assign values to variables. The score of a clause $C$ is defined as follows:

• If $C$ is satisfied then its score is 1.
• If $C$ is not satisfied and has $k$ unassigned literals then its score is $1-2^{-k}$.

Initially the score of each clause is $1-2^{-3} = 7/8$, and so the total score is $(7/8) m$. We now assign values to the variables $x_1,\ldots,x_n$ in order. Suppose that we have assigned values to variables $x_1,\ldots,x_{i-1}$, and the current total score is $S = S(C_1)+\cdots+S(C_m)$. Let $S_0,S_1$ the total score if we assign the values $0,1$ (respectively) to $x_i$. I claim that $S_0(C)+S_1(C) = 2S(C)$ for any clause $C$, and so $S_0 + S_1 = 2S$. Indeed:

• If $C$ is satisfied (only given $x_1,\ldots,x_{i-1}$) or doesn't contain $x_i$ then $S_0(C) + S_1(C) = 2S(C)$.
• Suppose that $C$ contains $k$ unassigned literals, including $x_i$. Then $S(C) = 1-2^{-k}$, $S_0(C) = 1-2^{-(k-1)}$, and $S_1(C) = 1$. Therefore $$ S_0(C) + S_1(C) = [1 - 2 \cdot 2^{-k}] + 1 = 2(1 - 2^{-k}) = 2S(C). $$
• A similar argument works when $C$ contains $\bar{x}_i$.

Since $S_0 + S_1 = 2S$, either $S_0 \geq S$ or $S_1 \geq S$ (possibly both). Therefore there is some assignment to $S$ such that after the assignment, the new score is at least $S$.

The initial score is $(7/8)m$ and the algorithm ensures that the score never decreases. At the end, the score of a clause $C$ is 1 if it is satisfied and $1-2^{-0}=0$ otherwise. Thus the final assignment satisfies at least $(7/8)m$ clauses.

Given that there is a deterministic algorithm, why are we interested in the randomized one? There are several reasons:

1. The randomized algorithm is much simpler.
2. The randomized algorithm is potentially faster.
3. The randomized algorithm can be converted to a deterministic one using the method of conditional expectations; we can think of it as a recipe for constructing a deterministic algorithm.

More generally, it is conjectured that every randomized polytime algorithm for a decision problem can be derandomized (this is the $\mathsf{P}=\mathsf{BPP}$ conjecture). Randomized algorithms will still be interesting for all the reasons enumerated above.