TAOCP 7.2.2.2 Exercise 299

Exercise 299. [HM23] Continuing the previous exercise, investigate the case $k = 2$.

Verified: no
Solve time: 5m30s

Solution

For $k=2$, the behavior of the random walk in Algorithm W becomes especially simple. Let $x^$ be a fixed satisfying assignment, and let $Y_t$ denote the number of variables on which the current assignment after $t$ flips differs from $x^$. The process terminates when $Y_t=0$.

Suppose that $Y_t=j>0$. The current assignment falsifies some clause $C$ chosen by Algorithm W. Since $x^$ satisfies $C$, at least one literal of $C$ has the value that it has in $x^$. The current assignment makes every literal of $C$ false, so every literal of $C$ whose value agrees with $x^*$ corresponds to a variable that is currently incorrect.

For a 2SAT clause, $C$ contains at most two literals. Algorithm W chooses one of the two variables of $C$ uniformly and flips it. Therefore, if at least one variable in $C$ is incorrect with respect to $x^*$, the probability of choosing such a variable is at least

$$ \frac12 . $$

Flipping a variable of $C$ that is incorrect with respect to $x^*$ decreases $Y_t$ by $1$. A flip of the other variable can increase $Y_t$ by $1$. Consequently, when $Y_t>0$,

$$ \Pr(Y_{t+1}=Y_t-1)\geq \frac12 , $$

and the walk is at least as favorable as the unbiased one-dimensional random walk on

$$ 0,1,\ldots,n $$

that moves left or right with equal probability and is absorbed at $0$.

For the unbiased walk starting at distance $j$, the expected time to hit $0$ is bounded by the expected time for the worst initial distance $j=n$. The standard gambler's ruin calculation gives

$$ E_j=j^2 . $$

Hence

$$ E(Y_0\text{-hitting time})\leq n^2 . $$

Therefore, a cutoff value of

$$ N=n^2 $$

flips gives a constant probability of reaching the satisfying assignment during one execution of Algorithm W. Repeating the algorithm independently raises the success probability in the usual way.

The special feature of $k=2$ is that every violated clause supplies a variable that moves the walk toward a fixed solution with probability at least $\frac12$. For larger $k$, the corresponding probability can be as small as $1/k$, so the quadratic bound obtained here does not extend unchanged.

Thus the recommended cutoff for the $2$SAT case is

$$ \boxed{N=n^2}. $$

This completes the proof. ∎