3-SAT Energy Landscape

Random 3-SAT phase transition at α ≈ 4.27 clauses/variable. Below: almost always satisfiable. Above: almost always unsatisfiable.

Instance

Variables n 20

Clause ratio α 4.27

Walk steps 200

SATISFIABLE

Clauses: —

Satisfied: —

Best: —

Phase transition α_c ≈ 4.267 (n→∞).
Below α_c: exponentially many solutions.
Above α_c: no solution exists (w.h.p.).

WalkSAT: flip variable in unsatisfied clause to minimize broken clauses. Energy = #unsat clauses.