The canonical NP-complete problem — near α≈4.27 the phase transition appears
Generate a formula to begin
0
SAT Clauses
0
UNSAT Clauses
Phase transition at α = M/N ≈ 4.27. Below: almost surely satisfiable. Above: almost surely unsatisfiable. At the boundary: exponentially hard for most algorithms.