The satisfiability conjecture for random k-SAT formulas. Human-friendly exposition of the recent OpenAI resolution
Source: arxiv.org/abs/2611.10139
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…
Comments and reviews
No comments yet.
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}'