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, numerical code, and manuscript preparation 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