Notes - Logic and Proof MT24, Walk-SAT

Created: October 14, 2024
Updated: December 23, 2024

Flashcards

The $\mathbf{3SAT}$ NP-complete decision problem is:

  • Input: 3CNF formula $\Phi$ (each clause has at most three literals) (suppose we have $m$ clauses)
  • Output: Whether $\Phi$ is satisfiable

Describe the $\mathbf{WalkSAT}$ @algorithm, which is a randomised algorithm for solving this problem, and @prove it runs in time $O(1.732^n)$ assuming that we want the correct answer with probability at least $1 - 10^{-4}$.

Suppose there are $n$ variables in $\Phi$. Then run the following several times (we will shortly see how many times several is in order to get a good chance of outputting the correct answer)

  • Let $\sigma$ be a random truth assignment to the variables
  • For $t = 1, 2, \cdots, 3n$:
    • If $\Phi$ is satisfied by $\sigma$, exit the loop
    • Otherwise, pick an unsatisfied clause $c$ and a variable $x$ in $c$ uniformly at random
    • Flip the value of $x$ in $\sigma$
  • See if $\sigma$ satisfies the formula

If any output $\sigma$ satisfies the formula, output that $\Phi$ is satisfiable, otherwise output that $\Phi$ is satisfiable.

We want to estimate the probability that one run of this algorithm generates a satisfying assignment.

Suppose:

  • $\sigma^\star$ is an arbitrary satisfying assignment of $\Phi$
  • $\sigma$ is the current truth assignment maintained in this run
  • $d _ t$ is the number of variables where $\sigma$ and $\sigma^\star$ disagree on step $t$ in this run

Then:

  • With probability $\ge 1/3$, $d _ {t+1} = d _ t - 1$ (i.e. we move closer to $\sigma^\star$)
  • With probability $\le 2/3$, $d _ {t _ 1} = d _ t + 1$ (i.e. we move further from $\sigma^\star$)

Why is this true? Consider an unsatisfied clause $(\ell _ 1 \vee \ell _ 2 \vee \ell _ 3)$ in $\Phi$. This clause is satisfied under $\sigma^\star$, so at least one of the variables needs to be opposite to its current value. With probability $\ge 1/3$ we pick a correct variable to flip, and with probability $\le 2/3$, we flip the wrong one.

Initially $P(d _ 0 \le n/2) \ge 1/2$. Then if this run is lucky, it satisfies $\Phi$ in the first $n/2$ steps. Thus the probability that this run satisfies $\Phi$ is

\[\text{prob. starts with at least n/2 correct} \times \text{makes n/2 steps in right direction}\]

which is equal to $\frac{1}{2 \cdot 3^{n/2} }$.

We can use the standard “boosting” technique in order to improve the probability of success, by running the algorithm multiple times. If we want the probability that it outputs the correct answer to be $\ge 1 - 10^{-4}$, then running it $20 \cdot 3^{n/2} \approx 1.732^n$ times gives the result.



Related posts