← 研踪 PaperTrailarXiv:2611.10139 · v1
The satisfiability conjecture for random k-SAT formulas. Human-friendly exposition of the recent OpenAI resolution
首次提交 2026-11-07 03:05
版本更新 2026-11-07 03:05
雷达观测 2026-11-10 10:11
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-07 03:05 · 最新观测版本
The satisfiability conjecture for random k-SAT formulas. Human-friendly exposition of the recent OpenAI resolution
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.
查看此版本解读 →查看此版本原文 ↗