On the Satisfiability Conjecture
On the Satisfiability Conjecture
-
Allan Sly, U.C. Berkeley
Fine Hall 314
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.