Mick gets what he needs

Cristopher Moore
University of New Mexico / Santa Fe Institute

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)

Presentation (PDF File)

Back to Phase Transitions And Algorithmic Complexity