pipette
ESEspañol

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

David Gamarnik

PreprintBold claims, read critically

In the authors' words

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 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 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.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.