← All problems

The satisfiability threshold conjecture for random k-SAT

22 years old · documented by

Let FF be a uniformly random proper kk-SAT formula with nn variables and cncn clauses, where each clause contains kk distinct variables, each possibly complemented, and clauses may be repeated. Write F(n,cn)F(n,cn) for this random formula, and let a property hold almost surely when its probability tends to 11 as n→∞n\rightarrow\infty.

Satisfiability threshold conjecture. For each kk there exists a threshold density ckc_k, such that for any positive ε\varepsilon, for all c<ck−εc<c_k-\varepsilon, F(n,cn)F(n,cn) is almost surely satisfiable, and for all c>ck+εc>c_k+\varepsilon, F(n,cn)F(n,cn) is almost surely unsatisfiable.

The conjecture asserts a sharp limiting satisfiability transition analogous to the known 22-SAT threshold. For large kk, satisfiability and unsatisfiability density bounds are asymptotically equal, but the existence of the threshold remains open in the source.

References
  1. 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

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 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 solutionHide 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

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size-September-25-2026/article.pdf

  • OpenAI-235-01-A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size.pdf213,536 bytesOpen
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 solutionHide 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

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Linear-Variance-of-the-Random-3-SAT-Hitting-Time-October-5-2026/linear-variance-of-the-random-3-sat-hitting-time.pdf

  • OpenAI-235-02-Linear-Variance-of-the-Random-3-SAT-Hitting-Time.pdf312,878 bytesOpen
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 solutionHide 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

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Variance-of-the-Random-k-SAT-Hitting-Time-September-27-2026/article.pdf

  • OpenAI-235-03-Variance-of-the-Random-k-SAT-Hitting-Time.pdf474,205 bytesOpen