Gamarnik writes a human-friendly account of OpenAI’s k-SAT proof
David Gamarnik published a detailed exposition of OpenAI’s proof of the satisfiability conjecture for random k-SAT, which says the probability of satisfiability drops sharply from near 1 to near 0 at a fixed ratio of clauses to variables.
Source published · In the Weekly Review of 15 November 2026
Filed under Mathematics, Probability
The conjecture concerns random formulas with \(n\) variables and \(m\) clauses of \(k\) literals each. It states that there is a threshold \(\alpha_k\) such that, as \(n\) grows, formulas with \(m/n\) below \(\alpha_k\) are satisfiable with probability tending to 1, and those above it with probability tending to 0. Ding, Sly and Sun proved it for large constant \(k\) about a decade ago with the second moment method.
The case of general \(k\) was settled recently, first by Carenini and shortly afterwards by OpenAI, whose internal model produced the proof among some 370 problems. Gamarnik’s note walks through the OpenAI argument step by step for readers who want to check it by hand.