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.
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.
Progress summary
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 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
- OpenAI-235-04-Computing-the-Random-3-SAT-Threshold.pdfOpen