On the Satisfiability Conjecture
On the Satisfiability Conjecture
-
Allan Sly, U.C. Berkeley
The random K-SAT model gives a model of random Boolean formulas and is perhaps the canonical random constraint satisfaction problem.听 The Satisfiability Conjecture posits that the probability of a satisfying assignment undergoes a sharp transition at a critical density of constraints.听 Heuristics developed in statistical physics predict the location of the transition as well as much more.听 I will survey what is known and predicted and describe recent progress establishing the conjecture for large enough K.听 This is joint work with Jian Ding and Allan Sly.