Random K-SAT

Random K-SAT is the study of Boolean satisfiability problems generated by choosing clauses uniformly at random. It is the canonical model system for algorithmic phase transitions: as the ratio of clauses to variables crosses a critical threshold, the problem shifts from almost surely satisfiable to almost surely unsatisfiable, with the hardest instances concentrated at the boundary. The randomness is not incidental — it is what makes the phase transition mathematically tractable, revealing structure that engineered instances obscure.

The satisfiability threshold for random 3-SAT is approximately 4.267. Below this threshold, the solution space is connected and solutions are plentiful. Above it, the solution space shatters into exponentially many clusters separated by vast Hamming deserts. The threshold itself is a phase transition in the sense of statistical mechanics, and its exact location has been determined using the replica symmetry breaking method from spin glass theory.