The satisfiability threshold conjecture for random k-SAT
Let be a uniformly random proper -SAT formula with variables and clauses, where each clause contains distinct variables, each possibly complemented, and clauses may be repeated. Write for this random formula, and let a property hold almost surely when its probability tends to as .
Satisfiability threshold conjecture. For each there exists a threshold density , such that for any positive , for all , is almost surely satisfiable, and for all , is almost surely unsatisfiable.
The conjecture asserts a sharp limiting satisfiability transition analogous to the known -SAT threshold. For large , satisfiability and unsatisfiability density bounds are asymptotically equal, but the existence of the threshold remains open in the source.
References
- Don Coppersmith, David Gamarnik, Mohammad Hajiaghayi and Gregory B. Sorkin, “Random MAX SAT, Random MAX CUT, and Their Phase Transitions”, arXiv:math/0306047 (2003).
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 3
Claimed by OpenAI. For every fixed k>=3, claims a finite positive limiting random k-SAT threshold for independent proper uniformly signed clauses sampled with replacement, with satisfiability tending to one below and zero above it. No equality-case assertion is made; the manuscript credits Gaia Carenini with priority for threshold existence.See full solution
The target uses proper clauses with distinct variables and allows repetitions, matching the independent uniformly signed with-replacement model. The source claims limiting thresholds for every fixed k>=3; k=2 is the known case. It makes no equality-case assertion and credits Carenini with threshold-existence priority.
GitHub repository: https://github.com/openai/math
- OpenAI-235-01-A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size.pdfOpen
Claimed by OpenAI. Claims variance Theta(n) for the first unsatisfiable prefix of proper uniform random 3-SAT sampled with replacement. The new assertion is an absolute linear upper bound; the matching lower bound is derived from Wilson's separation theorem. Clauses use three distinct variables.See full solution
This companion concerns fluctuations of the first-unsatisfiable prefix in the same proper with-replacement 3-SAT process. Linear variance is related threshold-process progress, not a separate determination of the limiting threshold value or its behavior at equality.
GitHub repository: https://github.com/openai/math
- OpenAI-235-02-Linear-Variance-of-the-Random-3-SAT-Hitting-Time.pdfOpen
Claimed by OpenAI. For proper uniformly signed random k-SAT with replacement, claims first-unsatisfiable-prefix variance Theta_k(n) for fixed k>=4 and an O(n log n) upper bound at k=3; matching capped lower bounds require the stated sufficiently late linear cap. Its k=3 logarithmic gap is closed only in the companion.See full solution
This companion concerns first-unsatisfiable-prefix fluctuations in the same proper with-replacement model. Its variance assertion is Theta_k(n) for fixed k>=4 and O(n log n) at k=3; capped lower bounds need the stated sufficiently late linear cap. The k=3 logarithmic gap is not closed in this manuscript.
GitHub repository: https://github.com/openai/math
- OpenAI-235-03-Variance-of-the-Random-k-SAT-Hitting-Time.pdfOpen