Paperlane

no. 12 · Tuesday 10 November 2026

The satisfiability conjecture for random k-SAT formulas. Human-friendly exposition of the recent OpenAI resolution

David Gamarnik

math.PR

Abstract

The satisfiability conjecture was one of the most important open problems in discrete probability. It was resolved recently first by Carenini~\cite{GCarenini}, and shortly after by OpenAI~\cite{k-sat-OpenAI}, among other 370 problems solved by its internal model. The conjecture concerned the satisfiability property of random instances of the k-SAT problem. It posits the existence of a fixed value for the clause-to-variables ratio around which the probability that the formula is satisfiable drops sharply from nearly one to nearly zero as the ratio increases. While the case of large constant $k$ was resolved a decade ago by Ding, Sly and Sun~\cite{ding2015proof,ding2022proof} using the heavy machinery of the second moment method, the case of general $k$ eluded proof until ~\cite{GCarenini} and~\cite{k-sat-OpenAI}. In this short note we provide a ''human-friendly'' and detailed exposition of the OpenAI's resolution of the conjecture.

fields
Probability
pdf ↗ page arXiv:2611.10139 ↗