Existence of sharp random k-SAT density thresholds
Follow the latest progress by email.
For each fixed k≥3, does random k-SAT have a limiting satisfiability threshold αₖ independent of formula size? Clauses are proper, uniformly signed, independent and sampled with replacement.
Why it matters and what counts as progress
Why it matters: A limiting density strengthens a sharp transition whose location could still vary with the number of variables.
What counts as progress: A positive finite αₖ with satisfiability tending to one below it and zero above it; behavior exactly at αₖ is a separate question.
How the problem developed
- 1999 · Threshold theorem [1]
Ehud Friedgut Proved a sharp threshold for random k-SAT, while the threshold location could still depend on the formula size; convergence to a fixed limiting density remained open.
- 25 Sept 2026 · Alternative proof [2]
OpenAI Released a proof that for every fixed k ≥ 3, random k-SAT with independently sampled, uniformly signed clauses on distinct variables has a finite positive limiting threshold.
Gaia Carenini Published a proof of the fixed-k satisfiability-threshold conjecture; the OpenAI manuscript credits this concurrent work with priority and presents an alternative proof.
AI contribution
A Limiting Satisfiability Threshold for Every Fixed Clause Size
For every fixed k≥3, random k-SAT with independent uniformly signed proper clauses sampled with replacement has a positive finite limiting density αₖ: satisfiability probability tends to one below αₖ and zero above it. The claim makes no assertion at αₖ.
Sources
Website timeline
Publication dates and editorial changes.
OpenAI formalizes an alternative proof of random k-SAT thresholds