Motivation
A local search can repair an unsatisfied constraint by changing one variable, but a repair may break a constraint that was already satisfied. For 2-SAT, a simple random walk still finds a satisfying assignment in polynomial expected time whenever one exists. Its analysis compares the current assignment with a fixed satisfying assignment that the algorithm never needs to know.
The probability of moving closer is at least one half at every unsuccessful step. Rather than assuming the steps are independent, we use a distance potential with a negative conditional drift. A finite time cap and independent restarts turn the expected-time argument into a one-sided error guarantee.
Definitions
Model and algorithm
Definition 5.3.1
(2-CNF formula)
A 2-CNF formula is a conjunction of clauses, each containing at most two literals. A literal is a Boolean variable or its negation. Remove tautological clauses and repeated literals within a clause; if an empty clause occurs, report unsatisfiable immediately. If no clauses remain, return any assignment. In the remaining case let be the number of variables and let every clause contain one or two distinct, nonopposite literals.
Definition 5.3.2
(Random-walk search)
Start from any assignment. While it does not satisfy the formula, choose any currently unsatisfied clause, select one of its variables uniformly, and flip that variable. The clause selection may depend on the entire past; the random choice among its variables is fresh and uniform conditional on that history. If the current assignment satisfies every clause, return it.
Theorems
Theorem 5.3.3
(Expected search time on satisfiable formulas)
If the formula has a satisfying assignment, the expected number of flips before the random walk first reaches any satisfying assignment is at most , from every starting assignment.
Theorem 5.3.4
(A capped one-sided randomized procedure)
Run the walk for at most flips and check the resulting assignment. On a satisfiable formula, the chance of finding no satisfying assignment in that run is at most . Repeating runs with fresh independent random choices makes the failure probability at most . Every returned assignment is verifiably satisfying, even if the formula is unsatisfiable.
The capped procedure returns “not found” if all runs fail. That outcome is not an unsatisfiability certificate. The theorem bounds its probability only when a satisfying assignment exists.
Proofs
A fixed satisfying assignment gives progress
Fix any satisfying assignment for the analysis. Let be the Hamming distance between the current assignment and , the number of variables on which they differ. The algorithm does not know and never computes .
Lemma 5.3.5
(Progress toward a fixed solution)
Let be a satisfying assignment and let be the Hamming distance from the current assignment to . At every step before a satisfying assignment is reached, conditional on the whole history, the next flip decreases by one with probability at least and otherwise increases it by one. If the chosen clause has one variable, or if , the decrease has probability one.
Proof
(Why a false clause gives progress)
At a nonsatisfying assignment, the chosen clause is false. Since satisfies it, at least one literal in that clause changes from false to true between the current assignment and . Its variable therefore differs from . A clause has at most two distinct variables, so a uniform flip decreases with conditional probability at least one half. Any flipped variable either agrees with and increases the distance by one, or disagrees and decreases it by one. For a one-literal clause the distance decreases with probability one.
If , every variable differs from , so every possible flip decreases the distance. If , the current assignment equals and is already satisfying. The distance process can depend on previous clause choices, but the conditional lower bound holds for every allowed history before termination.
A potential and its conditional drift
Proof
(Expected time via the potential)
Define for . It is nonnegative and at most . For , put . Then
If the probability of decreasing the distance is , the conditional expected change is at most
At , the distance decreases with probability one and . Thus, at every step before finding a satisfying assignment, the conditional expected potential decreases by at least one.
Let be the first time a satisfying assignment is reached, counting flips, and freeze the process after that time. Summing the conditional drift for the first possible flips and taking expectations gives
The left side is nonnegative, so . Letting tend to infinity and using monotone convergence yields . In particular the walk reaches a satisfying assignment almost surely. It may reach a satisfying assignment other than the fixed earlier; freezing at the first one only helps the argument.
Proof X-ray
Where the potential and the stopping time earn their keep
Each hypothesis is used at exactly one place. The clause-size bound of two gives the decrease probability , and for then makes ; at the decrease is certain. The non-obvious move is the quadratic potential. The distance itself has expected change , which is zero for a fair step and proves nothing about termination, whereas the concave turns every fair step into a drift of exactly .
The argument closes through a stopping time. The bound on holds for each finite , nonnegativity of turns it into a bound on , and monotone convergence lets . No Markov property of is used, only the drift bound given each history.
A drift bound is a statement about conditional expectations, not about individual flips.
Counterexample mode
A fair chance to move closer is not monotone progress
A flip can increase the distance to the fixed solution. For example, when a false two-literal clause contains one variable agreeing with and one disagreeing, a uniform flip moves in either direction with probability one half. Concretely, in the two-variable worked example below, the walk at has the false clause ; flipping gives , at distance from the solution , whereas the distance was . The proof uses expected decrease of a curved potential, not a claim that every flip improves the assignment.
Why this potential has the right shape
For an idealized unbiased walk on distances , suppose distance zero is absorbing and distance always moves to . If is its expected time to reach zero, the one-step equations suggest
for . Substituting satisfies all of these equations. That observation motivates the potential: it is the exact expected-time solution for the reference walk, and a process that is at least as likely to move downward has no larger conditional expected change for this increasing, concave function.
The proof does not require the actual distance process to be a Markov chain. Two histories can have the same distance but different current assignments and different available false clauses. The conditional drift inequality holds for each such history, so summing it remains valid. Treating distance as an independent symmetric random walk without justification would overlook this distinction.
The reference equations also explain why a linear distance potential is not sufficient here: a fair step can have zero expected change in distance, whereas the quadratic potential has a strictly negative second-difference contribution. The clause-size bound is also essential to this particular argument. With three distinct literals, a false clause need have only one variable that differs from a fixed satisfying assignment, giving a decrease probability as small as one third. For example, at the clause is false, while the satisfying assignment differs in only . A uniform choice of its three variables moves toward that chosen solution with probability one third. This does not prove that random walks cannot help with 3-SAT; it shows why the one-half drift proof cannot simply be reused unchanged.
Finally, the potential can stop at a positive value because the walk may reach a satisfying assignment different from the one fixed for the analysis. The telescoping bound only needs the stopped potential to be nonnegative. Requiring it to be exactly zero would add an unnecessary and generally false assumption.
From expected time to a finite cap
Proof
(Markov's inequality and restarts)
Markov's inequality gives . Checking the initial assignment and the assignment after each flip ensures that a satisfying state reached by the cap is returned. If one run fails, restart from any assignment using fresh random choices. The same conditional bound applies to each run, so the probability that all runs fail is at most .
On an unsatisfiable formula no assignment can pass the explicit clause check, so the procedure never returns a false satisfying assignment. Its “not found” outcome does not distinguish an unsatisfiable formula from an unlucky run on a satisfiable one. This is a randomized search guarantee, not a standalone proof of unsatisfiability.
With clauses, a straightforward implementation checks all clauses to find an unsatisfied one in time per flip and uses time to initialize an assignment. For capped runs this gives time after preprocessing, under constant-time literal evaluation. The variable choice in a two-literal clause uses one fair bit; a one-literal clause needs none. A run uses at most such bits. Faster deterministic algorithms for 2-SAT exist; this chapter analyzes the random-walk method rather than claiming it is the fastest approach.
Worked examples
Worked example 5.3.6
(A two-variable walk)
Consider , whose unique satisfying assignment is . Starting at , the first clause is false. Flipping either variable yields or , each with probability one half. From either state, the unique false clause contains one flip leading to and one flip returning to . Thus the chance of success within the first two flips is .
Worked example 5.3.7
(A unit clause)
For the formula , starting at selects the only variable and flips it to one. The walk succeeds in one flip. The conditional decrease probability is one, stronger than the lower bound one half.
Worked example 5.3.8
(An unsatisfiable instance)
For , no assignment satisfies both clauses. At either assignment exactly one unit clause is false, and the walk flips forever unless capped. The capped procedure returns “not found”; it never claims a satisfying assignment.
Worked example 5.3.9
(Restarts amplify success)
If a satisfiable formula is run independently four times with a cap of flips each, the chance that all four runs fail is at most . The runs may stop earlier when a satisfying assignment is found. The estimate is a worst-case bound, not an exact failure probability for every formula.
Common mistakes
Common mistake
(A false clause need not have all its variables wrong)
The fact that a false clause contains a variable differing from a particular solution does not mean every variable in that clause differs. Flipping a uniformly selected variable can move away from that solution. The proof needs only a conditional probability of at least one half for a decrease.
Common mistake
(Expected time is not a bound on every run)
An expected-time result does not supply a deterministic upper bound on every run. Random choices can revisit the same assignments repeatedly. The cap gives a finite procedure with a stated failure probability; repetition reduces that probability but does not make it zero after finitely many runs.
Common mistake
(A failed search does not prove unsatisfiability)
Finally, a failed randomized search is not a proof that the formula is unsatisfiable. Only a returned assignment is a certificate in this algorithm. A separate deterministic 2-SAT algorithm can decide both answers.
Summary
For a satisfiable 2-CNF formula, every false clause contains a variable disagreeing with a fixed solution. A random flip decreases Hamming distance with conditional probability at least one half. The potential has expected drift at most minus one until a satisfying assignment is found, giving an expected-flip bound. Capping and restarting yields a finite one-sided randomized search procedure.
Exercises
Quick check
(For the formula starting at , compute the number of flips and the potential drop for .)
Compute .
Solution · Answer
One flip changes to one and satisfies the clause. The distance from the solution goes from one to zero; and , so the potential drops by one.
Quick check
(In the two-variable worked example, compute the chance of success within two flips from .)
List the two equally likely first flips and follow each.
Solution · Answer
After the first flip the state is or . In either case, one of the two equally likely flips of the false clause reaches . Thus the probability is .
Quick check
(If each capped run fails with probability at most one half, how many independent runs suffice to make failure probability at most ?)
Solve .
Solution · Answer
Five runs suffice because .
Quick check
(Explain why returning “unsatisfiable” after a capped run fails would be unjustified.)
Could an unlucky run on a satisfiable formula look the same?
Solution · Answer
A satisfiable formula can have an unlucky sequence of flips that does not reach a satisfying assignment before the cap. The algorithm only controls the probability of such failure; it does not produce a certificate that no assignment exists.