TOPICS
Search

Random k-SAT


Random k-SAT is a random satisfiability problem in which a formula on n Boolean variables is a conjunction of m independently sampled clauses. Each clause is a disjunction of k distinct uniformly chosen variables, each independently negated with probability 1/2. The ratio m/n is the clause density. Clauses may be repeated.

Vorobyev (2026) reported that for k=3 and m=|_4.268n_|, the formula is unsatisfiable with probability tending to 1 as n->infty. Thus 4.268 is an upper bound on the random 3-SAT satisfiability threshold, not its exact value. Here |_x_| is the floor function. Vorobyev (2026) states that large language models drove the mathematical argument, Lean formalization, and numerical code under the author's direction.


See also

Satisfiability Problem

Explore with Wolfram|Alpha

References

Vorobyev, F. "An Upper Bound of 4.268 for the Random 3-SAT Satisfiability Threshold." 6 Oct 2026. https://arxiv.org/abs/2610.10599.

Cite this as:

Weisstein, Eric W. "Random k-SAT." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Randomk-SAT.html

Subject classifications