Does the conjecture give one threshold for all k?

No. The constant depends on the clause size and the random model.

Does a threshold theorem describe the exact boundary probability?

Not necessarily. The usual statement specifies fixed densities strictly below and above the threshold.

Does proving existence determine a simple numerical value?

No. Existence, computability and an explicit numerical characterization are distinct achievements.

AI Glossary / Graphs and symbolic AI / Advanced

Satisfiability threshold conjecture

Definition

The satisfiability threshold conjecture is the historical claim that, for each fixed clause size k in a standard random k-SAT model, a constant clause-to-variable density separates formulas that are almost surely satisfiable from those that are almost surely unsatisfiable as the number of variables grows.

What it means

The question concerns a probability distribution over formulas, not a rule deciding every individual formula. Below the proposed threshold, the probability of satisfiability approaches one; above it, that probability approaches zero. The statement normally leaves behavior exactly at the threshold unspecified.

The word conjecture is historically important but needs a dated status note. Ding, Sly and Sun established the threshold for sufficiently large k. As of 15 October 2026, recent preprints claim the general fixed-k result; the established large-k theorem and these new claims should be distinguished.

This entry explains the mathematical question and attributes the recent reports. The source statements were checked, but their complete proofs and formalizations were not independently audited here. Attribution records what the preprints claim without certifying their arguments or acceptance.

How it works

In a standard model, select n Boolean variables and m random clauses, each containing k distinct variables with independently chosen signs. Clauses are sampled independently, commonly with replacement. The density is alpha = m/n, with m usually taken as the integer part of alpha n.

For fixed k, the conjectured constant alpha_k governs the large-n limit. At any fixed density below alpha_k, satisfiability should become overwhelmingly likely. At any fixed density above it, unsatisfiability should become overwhelmingly likely.

Adding clauses cannot make a fixed formula easier to satisfy, but that monotonicity alone does not prove a limiting constant threshold. A sharp transition whose location depends on n is also different from proving that its location converges.

Determining the threshold's existence, estimating its numerical value and efficiently solving formulas near it are separate problems. A proof of existence need not supply a practical algorithm for finding satisfying assignments.

Three practical examples

1. Solver research: Researchers generate random formulas at several clause densities to study changes in satisfiability and algorithm behavior. They specify the generation model rather than assuming all random instances are equivalent.

2. Probability theory: The threshold question provides an example of an abrupt large-system transition arising from many local constraints.

3. Benchmark interpretation: An evaluator distinguishes a solver timing experiment from evidence about the mathematical existence or location of a limiting satisfiability threshold.

Think of it this way

Think of adding constraints to a large puzzle until compatible solutions become rare. The threshold question asks whether the transition concentrates around a fixed constraints-per-variable ratio in a specified random puzzle family.

The analogy does not imply a universal ratio for every puzzle. The random model, clause size and asymptotic limit are essential, and finite examples can behave differently on either side of a proposed boundary.

Worked example

Consider uniformly signed random 3-SAT with independent clauses. For any fixed truth assignment, exactly one of the eight possible sign patterns on three selected variables makes all three literals false. A random clause is therefore satisfied by that assignment with probability 7/8.

With m independently sampled clauses, that assignment satisfies the full formula with probability (7/8)^m. There are 2^n assignments, so the expected number of satisfying assignments is 2^n × (7/8)^m.

For the small illustration n=10 and m=20, this expectation is approximately 70.9. That does not prove that a randomly generated formula is satisfiable: an expectation does not describe every instance, and solution events are dependent.

More generally, with m approximately alpha n, the expectation decays exponentially when 2 × (7/8)^alpha is below one, giving an elementary upper-bound argument. This first-moment calculation does not identify the exact 3-SAT threshold.

Illustrative case study

In a fictional project, Alder Benchmarks times a solver on a small collection of random formulas. Its report calls the density at which half the samples were solved “the satisfiability threshold.”

The review separates solver completion from actual satisfiability, records timeouts as unresolved and repeats the study across formula sizes and independent samples. It describes the observed finite-sample transition without claiming a proof of an asymptotic theorem.

The case illustrates why empirical curves and mathematical thresholds must be kept distinct. A solver's resource limit can change the apparent curve even when the underlying formula distribution is unchanged.

Common misconceptions and mistakes

A threshold decides every formula by its density. The statement is probabilistic and asymptotic.
Sharp transition and convergent threshold are identical claims. The transition location can still depend on size.
Expected solution count equals probability of satisfiability. These are different quantities.
A proof for large k automatically covers k=3. Its stated range must be respected.
The historical word conjecture fixes the current research status. New results require the glossary to distinguish historical terminology from dated evidence.

Business use

This topic is most relevant to research evaluation and understanding computational difficulty. It does not provide a shortcut for deciding whether a particular business configuration is feasible.

When using random SAT benchmarks, document clause size, sampling rules, density, variable count and solver limits. Separate satisfiable, unsatisfiable and unresolved outcomes. Do not generalize conclusions from uniform random formulas to structured industrial formulas without evidence.

Research-status statements deserve particular care. The 5 October 2026 ECCC preprint claims a general fixed-k proof, while a separate repository describes formalized threshold and computability results. These are dated research claims, not evidence here of completed journal review or consensus.

Check your understanding

Why does an expected count of about 70.9 satisfying assignments not prove that every sampled formula is satisfiable?

Answer: The expectation averages solution counts across formulas. Some can have no solutions while others have many, producing the same positive average.

Related terms

Satisfiability
Random k-SAT
phase transition
clause density
sharp threshold
first-moment method
asymptotic probability
SAT benchmark

Learn next

For a chosen k, derive the probability that a fixed assignment satisfies one uniformly signed clause. Extend it to m independent clauses, then explain why the resulting expected count gives limited information about individual formulas.

Sources

Ding, Sly and Sun's large-k result: https://arxiv.org/abs/1411.0650

Carenini, posted 5 October 2026, Corollary 1.2; statement reviewed, proof unaudited: https://eccc.weizmann.ac.il/report/2026/229/download

Formalization scope and computability claims: https://github.com/openai/math/blob/main/lean/docs/235.md

The expectation calculation and Alder Benchmarks case are original illustrations. Recent preprint claims are attributed as of 15 October 2026; no independent proof audit or journal acceptance is claimed.

Previous: Satisfiability Next: Satisficing