TOPICS
Search

Satisfiability Problem

The satisfiability problem asks whether a given Boolean formula in conjunctive normal form has an assignment that makes the formula "true." Cook (1971) showed that the problem is NP-complete.

Carenini (2026) announced existence of a limiting satisfiability threshold for every fixed clause size k>=3. In the model of independent uniformly signed clauses on k distinct variables, sampled with replacement, there is a finite positive alpha_k such that the probability of satisfiability with |_cn_| clauses tends to 1 for c<alpha_k and to 0 for c>alpha_k as the number n of variables tends to infinity. Here |_·_| is the floor function.

Vorobyev (2026) reported a quantitative upper bound on the satisfiability threshold for random k-SAT with k=3.

See also

3SAT, Boolean Algebra, Exponential Time Hypothesis, Random k-SAT, Satisfiable

Explore with Wolfram|Alpha

References

Carenini, G. "A Polynomial Scaling Window for Random k-SAT and a Proof of the Satisfiability Conjecture." Electronic Colloquium on Computational Complexity, Report TR26-229, 2026. https://eccc.weizmann.ac.il/report/2026/229/.Cook, S. A. "The Complexity of Theorem-Proving Procedures." In Proc. Third Annual ACM Symposium on Theory of Computing. New York: Association for Computing Machinery, pp. 151-158, 1971. https://doi.org/10.1145/800157.805047.Cook, S. A. and Mitchell, D. G. "Finding Hard Instances of the Satisfiability Problem: A Survey." In Satisfiability Problem: Theory and Applications (Piscataway, NJ, 1996) (Ed. D. Du, J. Gu, and P. M. Pardalos). Providence, RI: Amer. Math. Soc., pp. 1-17, 1997.Vorobyev, F. "An Upper Bound of 4.268 for the Random 3-SAT Satisfiability Threshold." 6 Oct 2026. https://arxiv.org/abs/2610.10599.

Referenced on Wolfram|Alpha

Satisfiability Problem

Cite this as:

Weisstein, Eric W. "Satisfiability Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SatisfiabilityProblem.html

Subject classifications