A polynomial scaling window for random k-SAT and a proof of the satisfiability conjectureResearch Paper
A random -SAT formula on Boolean variables is a conjunction of independent uniformly random clauses, each a disjunction of literals on distinct variables. As clauses are added, the formula passes from satisfiable to unsatisfiable, and the question of where and how fast this happens has driven work in probabilistic combinatorics, statistical physics…