Delphi.science

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

Source: arxiv.org/abs/2611.10139

David Gamarnik

arXivarxiv/2611.10139Nov 6, 2026math.PRscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.10139
curl -X POST /api/v1/records/arxiv/2611.10139/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.10139/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'