Abstract

We establish that the asymptotic order of the satisfiability threshold is Theta(2^k). This solves the "Y2^K" problem which remained open for more than fifteen years. As a bonus feature, our proof offers a first, blurry (but rigorous) view of the geometry of the set of solutions.

(Joint work with Dimitris Achlioptas of Microsoft Research)