7
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.