Critical Behavior in the Satisfiability of Random Boolean Expressions

Scott Kirkpatrick; Bart Selman

doi:10.1126/science.264.5163.1297

journal article May 27, 1994

Critical Behavior in the Satisfiability of Random Boolean Expressions

Scott Kirkpatrick Bart Selman

Science Vol. 264 No. 5163 pp. 1297-1301 · American Association for the Advancement of Science (AAAS)

View at Publisher Save 10.1126/science.264.5163.1297

Abstract

Determining the satisfiability of randomly generated Boolean expressions with
k
variables per clause is a popular test for the performance of search algorithms in artificial intelligence and computer science. It is known that for
k
= 2, formulas are almost always satisfiable when the ratio of clauses to variables is less than 1; for ratios larger than 1, the formulas are almost never satisfiable. Similar sharp threshold behavior is observed for higher values of
k
. Finite-size scaling, a method from statistical physics, can be used to characterize size-dependent effects near the threshold. A relationship can be drawn between thresholds and computational complexity.

Topics

No keywords indexed for this article. Browse by subject →

References

25

[1]

A linear-time algorithm for testing the truth of certain quantified boolean formulas

Bengt Aspvall, Michael F. Plass, Robert Endre Tarjan

Information Processing Letters 1979 10.1016/0020-0190(79)90002-4

[2]

Barber, M. N., Phase Transitions and Critical Phenomena 8: 145 (1983).

[3]

Bollobas B. Random Graphs (1985).

[4]

Broder, A. Z., Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms: 322 (1993).

[5]

Cheeseman, P., Proceedings of the 12th International Conference on Artificial Intelligence: 331 (1991).

[6]

Chvatal, V., Proceedings of the 33rd Annual Symposium on Foundations of Computer Science: 629 (1992).

[7]

CLEARWATER, S.H., COOPERATIVE SOLUTION OF CONSTRAINT SATISFACTION PROBLEMS, SCIENCE 254: 1181 (1991). 10.1126/science.254.5035.1181

[8]

Cook, S. A., Proceedings of the 3rd Annual ACM Symposium on Theory of Computing: 151 (1971).

[9]

Crawford, J., Proceedings of the 11th National Conference on Artificial Intelligence: 21 (1993).

[10]

DAVIS, M, A COMPUTING PROCEDURE FOR QUANTIFICATION THEORY, JOURNAL OF THE ACM 7: 201 (1960). 10.1145/321033.321034

[11]

Dubois O. Proceedings of the 2nd DIMACS Implementation Challenge (1996).

[12]

Erdos, P., Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5: 17 (1960).

[13]

Fu, Y. T., Lectures in the Sciences of Complexity: 815 (1989).

[14]

Goerdt, A., Proceedings of the 17th International Symposium on the Mathematical Foundation of Computer Science: 264 (1990).

[15]

Janson, S., Random Structures & Algorithms 4: 233 (1993). 10.1002/rsa.3240040303

[16]

KAMATH, A.P., ANN OPER RES 25: 43 (1990). 10.1007/bf02283686

[17]

KIRKPATRICK, S, STATISTICAL-MECHANICS AND DISORDERED-SYSTEMS, COMMUNICATIONS OF THE ACM 28: 363 (1985). 10.1145/3341.3344

[18]

Kirkpatrick S. Advances in Neural Information Processing Systems 6 (1993).

[19]

Larrabee, T., Proceedings of the AAAI Symposium on Artificial Intelligence and NP-Hard Problems: 112 (1993).

[20]

Spin Glass Theory and Beyond

M Mezard, G Parisi, M Virasoro

World Scientific Lecture Notes in Physics 10.1142/0271

[21]

Mitchell, D., Artificial Intelligence 81: 17 (1996). 10.1016/0004-3702(95)00045-3

[22]

Mitchell, D., Proceedings of the 10th National Conference on Artificial Intelligence: 459 (1992).

[23]

SELMAN, B, Proceedings of the 10th National Conference on Artificial Intelligence: 440 (1992).

[24]

Spencer J. Ten Lectures on the Probabilistic Method (1987).

[25]

Stauffer D. Introduction to Percolation Theory (1992).

Cited By

363

Zeno-effect computation: Opportunities and challenges

Jesse Berwald, Nicholas Chancellor · 2025

Physical Review A

Evolutionary Game-Theoretic Approach to the Population Dynamics of Early Replicators

Matheus Mariano, José Fontanari · 2024

Life

Edwards statistical mechanics for jammed granular matter

Adrian Baule, Flaviano Morone · 2018

Reviews of Modern Physics

A continuous-time MaxSAT solver with high analog performance

Botond Molnár, Ferenc Molnar · 2018

Nature Communications

Information, Physics, and Computation

Marc Mézard, Andrea Montanari · 2009

The probabilistic analysis of a greedy satisfiability algorithm

Alexis C. Kaporis, Lefteris M. Kirousis · 2005

Random Structures & Algorithms

RandomK-satisfiability problem: From an analytic solution to an efficient algorithm

Marc Mézard, Riccardo Zecchina · 2002

Physical Review E

Local Search Algorithms for SAT: An Empirical Evaluation

Holger H. Hoos, Thomas Stützle · 2000

Journal of Automated Reasoning

Critical behavior in the computational cost of satisfiability testing

Bart Selman, Scott Kirkpatrick · 1996

Artificial Intelligence

Entropy of theK-Satisfiability Problem

Rémi Monasson, Riccardo Zecchina · 1996

Physical Review Letters

Metrics

363

Citations

25

References

Details

Published: May 27, 1994
Vol/Issue: 264(5163)
Pages: 1297-1301

Authors

S

Scott Kirkpatrick

IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598, USA. E-mail: kirk@watson.ibm.com

B

Bart Selman

IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598, USA. E-mail: kirk@watson.ibm.com

Cite This Article

Scott Kirkpatrick, Bart Selman (1994). Critical Behavior in the Satisfiability of Random Boolean Expressions. Science, 264(5163), 1297-1301. https://doi.org/10.1126/science.264.5163.1297

Critical Behavior in the Satisfiability of Random Boolean Expressions

You May Also Like