← All problems

Exact satisfiability threshold for random k-SAT for small k (k = 3)

In the uniform random 3-SAT model, choose a 3-CNF formula with n variables and m clauses uniformly from formulas whose clauses contain three distinct literals. Determine the exact constant r_3 such that, as n tends to infinity with m/n tending to r, satisfiability has probability tending to 1 for r < r_3 and tending to 0 for r > r_3.

Source: I. Caragiannis, N. Gravin, and Z. Jiang, On the Satisfiability of Random 3-SAT Formulas with k-Wise Independent Clauses, LIPIcs ESA 2025, Article 103, Introduction..

Status Open Status review date not recorded in this edition

Listed by ProofAtlas. Status qualification is attributed to ProofAtlas; no full resolution is certified here.

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 1

Claimed by OpenAI. Claims the limiting proper uniform random 3-SAT threshold is a positive computable real, approximable by one deterministic oracle-free Turing machine from unary precision alone. No efficiency bound, behavior at the threshold, or computability for other clause sizes is asserted; existence priority is credited to Carenini.See full solutionHide full solution

This is computability progress toward the limiting proper uniform 3-SAT threshold. The source asserts an oracle-free precision-only deterministic approximation algorithm, not an explicit numerical formula, computational efficiency, or behavior exactly at the threshold. Its proper clauses use three distinct variables.

GitHub repository: https://github.com/openai/math

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Computing-the-Random-3-SAT-Threshold-September-27-2026/article.pdf

  • OpenAI-235-04-Computing-the-Random-3-SAT-Threshold.pdf612,468 bytesOpen