DOI: 10.1126/science.264.5163.1297. Critical Behavior in the Satisfiability of Random Boolean Expressions

Critical Behavior in the Satisfiability of Random Boolean Expressions

10.1126/science.264.5163.1297

Crossref journal-article

American Association for the Advancement of Science (AAAS)

Science (221)

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.

Bibliography

Kirkpatrick, S., & Selman, B. (1994). Critical Behavior in the Satisfiability of Random Boolean Expressions. Science, 264(5163), 1297â1301.

Authors 2

Scott Kirkpatrick (first)
Bart Selman (additional)

References 25 Referenced 355

ASPVALL, B, LINEAR-TIME ALGORITHM FOR TESTING THE TRUTH OF CERTAIN QUANTIFIED BOOLEAN FORMULAS, INFORMATION PROCESSING LETTERS 8: 121 (1979). (10.1016/0020-0190(79)90002-4) / INFORMATION PROCESSING LETTERS (1979)
Barber, M. N., Phase Transitions and Critical Phenomena 8: 145 (1983). / Phase Transitions and Critical Phenomena (1983)
Bollobas B. Random Graphs (1985).
Broder, A. Z., Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms: 322 (1993). / Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (1993)
Cheeseman, P., Proceedings of the 12th International Conference on Artificial Intelligence: 331 (1991). / Proceedings of the 12th International Conference on Artificial Intelligence (1991)
Chvatal, V., Proceedings of the 33rd Annual Symposium on Foundations of Computer Science: 629 (1992). / Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (1992)
CLEARWATER, S.H., COOPERATIVE SOLUTION OF CONSTRAINT SATISFACTION PROBLEMS, SCIENCE 254: 1181 (1991). (10.1126/science.254.5035.1181) / SCIENCE (1991)
Cook, S. A., Proceedings of the 3rd Annual ACM Symposium on Theory of Computing: 151 (1971). / Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (1971)
Crawford, J., Proceedings of the 11th National Conference on Artificial Intelligence: 21 (1993). / Proceedings of the 11th National Conference on Artificial Intelligence (1993)
DAVIS, M, A COMPUTING PROCEDURE FOR QUANTIFICATION THEORY, JOURNAL OF THE ACM 7: 201 (1960). (10.1145/321033.321034) / JOURNAL OF THE ACM (1960)
Dubois O. Proceedings of the 2nd DIMACS Implementation Challenge (1996).
Erdos, P., Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5: 17 (1960). / Publications of the Mathematical Institute of the Hungarian Academy of Sciences (1960)
Fu, Y. T., Lectures in the Sciences of Complexity: 815 (1989). / Lectures in the Sciences of Complexity (1989)
Goerdt, A., Proceedings of the 17th International Symposium on the Mathematical Foundation of Computer Science: 264 (1990). / Proceedings of the 17th International Symposium on the Mathematical Foundation of Computer Science (1990)
Janson, S., Random Structures & Algorithms 4: 233 (1993). (10.1002/rsa.3240040303) / Random Structures & Algorithms (1993)
KAMATH, A.P., ANN OPER RES 25: 43 (1990). (10.1007/BF02283686) / ANN OPER RES (1990)
KIRKPATRICK, S, STATISTICAL-MECHANICS AND DISORDERED-SYSTEMS, COMMUNICATIONS OF THE ACM 28: 363 (1985). (10.1145/3341.3344) / COMMUNICATIONS OF THE ACM (1985)
Kirkpatrick S. Advances in Neural Information Processing Systems 6 (1993).
Larrabee, T., Proceedings of the AAAI Symposium on Artificial Intelligence and NP-Hard Problems: 112 (1993). / Proceedings of the AAAI Symposium on Artificial Intelligence and NP-Hard Problems (1993)
Mezard M. Spin Glass Theory and Beyond (1986). (10.1142/0271)
Mitchell, D., Artificial Intelligence 81: 17 (1996). (10.1016/0004-3702(95)00045-3) / Artificial Intelligence (1996)
Mitchell, D., Proceedings of the 10th National Conference on Artificial Intelligence: 459 (1992). / Proceedings of the 10th National Conference on Artificial Intelligence (1992)
SELMAN, B, Proceedings of the 10th National Conference on Artificial Intelligence: 440 (1992). / Proceedings of the 10th National Conference on Artificial Intelligence (1992)
Spencer J. Ten Lectures on the Probabilistic Method (1987).
Stauffer D. Introduction to Percolation Theory (1992).

Dates

Type	When
Created	18 years, 10 months ago (Oct. 5, 2006, 8:01 p.m.)
Deposited	1 year, 7 months ago (Jan. 12, 2024, 6:53 p.m.)
Indexed	3 weeks ago (Aug. 6, 2025, 9:31 a.m.)
Issued	31 years, 3 months ago (May 27, 1994)
Published	31 years, 3 months ago (May 27, 1994)
Published Print	31 years, 3 months ago (May 27, 1994)

Funders 0

None

BibTeX

@article{Kirkpatrick_1994, title={Critical Behavior in the Satisfiability of Random Boolean Expressions}, volume={264}, ISSN={1095-9203}, url={http://dx.doi.org/10.1126/science.264.5163.1297}, DOI={10.1126/science.264.5163.1297}, number={5163}, journal={Science}, publisher={American Association for the Advancement of Science (AAAS)}, author={Kirkpatrick, Scott and Selman, Bart}, year={1994}, month=may, pages={1297–1301} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        6
      ]
    ],
    "date-time": "2025-08-06T13:31:48Z",
    "timestamp": 1754487108103
  },
  "reference-count": 25,
  "publisher": "American Association for the Advancement of Science (AAAS)",
  "issue": "5163",
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        1994,
        5,
        27
      ]
    ]
  },
  "abstract": "<jats:p>\n            Determining the satisfiability of randomly generated Boolean expressions with\n            <jats:italic>k</jats:italic>\n            variables per clause is a popular test for the performance of search algorithms in artificial intelligence and computer science. It is known that for\n            <jats:italic>k</jats:italic>\n            = 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\n            <jats:italic>k</jats:italic>\n            . 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.\n          </jats:p>",
  "DOI": "10.1126/science.264.5163.1297",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2006,
        10,
        6
      ]
    ],
    "date-time": "2006-10-06T00:01:25Z",
    "timestamp": 1160092885000
  },
  "page": "1297-1301",
  "source": "Crossref",
  "is-referenced-by-count": 355,
  "title": "Critical Behavior in the Satisfiability of Random Boolean Expressions",
  "prefix": "10.1126",
  "volume": "264",
  "author": [
    {
      "given": "Scott",
      "family": "Kirkpatrick",
      "sequence": "first",
      "affiliation": [
        {
          "name": "IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598, USA. E-mail: kirk@watson.ibm.com"
        }
      ]
    },
    {
      "given": "Bart",
      "family": "Selman",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598, USA. E-mail: kirk@watson.ibm.com"
        }
      ]
    }
  ],
  "member": "221",
  "reference": [
    {
      "key": "e_1_2_1_1_1",
      "doi-asserted-by": "crossref",
      "first-page": "121",
      "DOI": "10.1016/0020-0190(79)90002-4",
      "volume": "8",
      "year": "1979",
      "unstructured": "ASPVALL, B, LINEAR-TIME ALGORITHM FOR TESTING THE TRUTH OF CERTAIN QUANTIFIED BOOLEAN FORMULAS, INFORMATION PROCESSING LETTERS 8: 121 (1979).",
      "journal-title": "INFORMATION PROCESSING LETTERS"
    },
    {
      "key": "e_1_2_1_2_1",
      "first-page": "145",
      "volume": "8",
      "year": "1983",
      "unstructured": "Barber, M. N., Phase Transitions and Critical Phenomena 8: 145 (1983).",
      "journal-title": "Phase Transitions and Critical Phenomena"
    },
    {
      "key": "e_1_2_1_3_1",
      "unstructured": "Bollobas B. Random Graphs (1985)."
    },
    {
      "key": "e_1_2_1_4_1",
      "first-page": "322",
      "year": "1993",
      "unstructured": "Broder, A. Z., Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms: 322 (1993).",
      "journal-title": "Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms"
    },
    {
      "key": "e_1_2_1_5_1",
      "first-page": "331",
      "year": "1991",
      "unstructured": "Cheeseman, P., Proceedings of the 12th International Conference on Artificial Intelligence: 331 (1991).",
      "journal-title": "Proceedings of the 12th International Conference on Artificial Intelligence"
    },
    {
      "key": "e_1_2_1_6_1",
      "first-page": "629",
      "year": "1992",
      "unstructured": "Chvatal, V., Proceedings of the 33rd Annual Symposium on Foundations of Computer Science: 629 (1992).",
      "journal-title": "Proceedings of the 33rd Annual Symposium on Foundations of Computer Science"
    },
    {
      "key": "e_1_2_1_7_1",
      "doi-asserted-by": "crossref",
      "first-page": "1181",
      "DOI": "10.1126/science.254.5035.1181",
      "volume": "254",
      "year": "1991",
      "unstructured": "CLEARWATER, S.H., COOPERATIVE SOLUTION OF CONSTRAINT SATISFACTION PROBLEMS, SCIENCE 254: 1181 (1991).",
      "journal-title": "SCIENCE"
    },
    {
      "key": "e_1_2_1_8_1",
      "first-page": "151",
      "year": "1971",
      "unstructured": "Cook, S. A., Proceedings of the 3rd Annual ACM Symposium on Theory of Computing: 151 (1971).",
      "journal-title": "Proceedings of the 3rd Annual ACM Symposium on Theory of Computing"
    },
    {
      "key": "e_1_2_1_9_1",
      "first-page": "21",
      "year": "1993",
      "unstructured": "Crawford, J., Proceedings of the 11th National Conference on Artificial Intelligence: 21 (1993).",
      "journal-title": "Proceedings of the 11th National Conference on Artificial Intelligence"
    },
    {
      "key": "e_1_2_1_10_1",
      "doi-asserted-by": "crossref",
      "first-page": "201",
      "DOI": "10.1145/321033.321034",
      "volume": "7",
      "year": "1960",
      "unstructured": "DAVIS, M, A COMPUTING PROCEDURE FOR QUANTIFICATION THEORY, JOURNAL OF THE ACM 7: 201 (1960).",
      "journal-title": "JOURNAL OF THE ACM"
    },
    {
      "key": "e_1_2_1_11_1",
      "unstructured": "Dubois O. Proceedings of the 2nd DIMACS Implementation Challenge (1996)."
    },
    {
      "key": "e_1_2_1_12_1",
      "first-page": "17",
      "volume": "5",
      "year": "1960",
      "unstructured": "Erdos, P., Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5: 17 (1960).",
      "journal-title": "Publications of the Mathematical Institute of the Hungarian Academy of Sciences"
    },
    {
      "key": "e_1_2_1_13_1",
      "first-page": "815",
      "year": "1989",
      "unstructured": "Fu, Y. T., Lectures in the Sciences of Complexity: 815 (1989).",
      "journal-title": "Lectures in the Sciences of Complexity"
    },
    {
      "key": "e_1_2_1_14_1",
      "first-page": "264",
      "year": "1990",
      "unstructured": "Goerdt, A., Proceedings of the 17th International Symposium on the Mathematical Foundation of Computer Science: 264 (1990).",
      "journal-title": "Proceedings of the 17th International Symposium on the Mathematical Foundation of Computer Science"
    },
    {
      "key": "e_1_2_1_15_1",
      "doi-asserted-by": "crossref",
      "first-page": "233",
      "DOI": "10.1002/rsa.3240040303",
      "volume": "4",
      "year": "1993",
      "unstructured": "Janson, S., Random Structures & Algorithms 4: 233 (1993).",
      "journal-title": "Random Structures & Algorithms"
    },
    {
      "key": "e_1_2_1_16_1",
      "doi-asserted-by": "crossref",
      "first-page": "43",
      "DOI": "10.1007/BF02283686",
      "volume": "25",
      "year": "1990",
      "unstructured": "KAMATH, A.P., ANN OPER RES 25: 43 (1990).",
      "journal-title": "ANN OPER RES"
    },
    {
      "key": "e_1_2_1_17_1",
      "doi-asserted-by": "crossref",
      "first-page": "363",
      "DOI": "10.1145/3341.3344",
      "volume": "28",
      "year": "1985",
      "unstructured": "KIRKPATRICK, S, STATISTICAL-MECHANICS AND DISORDERED-SYSTEMS, COMMUNICATIONS OF THE ACM 28: 363 (1985).",
      "journal-title": "COMMUNICATIONS OF THE ACM"
    },
    {
      "key": "e_1_2_1_18_1",
      "unstructured": "Kirkpatrick S. Advances in Neural Information Processing Systems 6 (1993)."
    },
    {
      "key": "e_1_2_1_19_1",
      "first-page": "112",
      "year": "1993",
      "unstructured": "Larrabee, T., Proceedings of the AAAI Symposium on Artificial Intelligence and NP-Hard Problems: 112 (1993).",
      "journal-title": "Proceedings of the AAAI Symposium on Artificial Intelligence and NP-Hard Problems"
    },
    {
      "key": "e_1_2_1_20_1",
      "doi-asserted-by": "crossref",
      "unstructured": "Mezard M. Spin Glass Theory and Beyond (1986).",
      "DOI": "10.1142/0271"
    },
    {
      "key": "e_1_2_1_21_1",
      "doi-asserted-by": "crossref",
      "first-page": "17",
      "DOI": "10.1016/0004-3702(95)00045-3",
      "volume": "81",
      "year": "1996",
      "unstructured": "Mitchell, D., Artificial Intelligence 81: 17 (1996).",
      "journal-title": "Artificial Intelligence"
    },
    {
      "key": "e_1_2_1_22_1",
      "first-page": "459",
      "year": "1992",
      "unstructured": "Mitchell, D., Proceedings of the 10th National Conference on Artificial Intelligence: 459 (1992).",
      "journal-title": "Proceedings of the 10th National Conference on Artificial Intelligence"
    },
    {
      "key": "e_1_2_1_23_1",
      "first-page": "440",
      "year": "1992",
      "unstructured": "SELMAN, B, Proceedings of the 10th National Conference on Artificial Intelligence: 440 (1992).",
      "journal-title": "Proceedings of the 10th National Conference on Artificial Intelligence"
    },
    {
      "key": "e_1_2_1_24_1",
      "unstructured": "Spencer J. Ten Lectures on the Probabilistic Method (1987)."
    },
    {
      "key": "e_1_2_1_25_1",
      "unstructured": "Stauffer D. Introduction to Percolation Theory (1992)."
    }
  ],
  "container-title": "Science",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://www.science.org/doi/pdf/10.1126/science.264.5163.1297",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2024,
        1,
        12
      ]
    ],
    "date-time": "2024-01-12T23:53:11Z",
    "timestamp": 1705103591000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://www.science.org/doi/10.1126/science.264.5163.1297"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1994,
        5,
        27
      ]
    ]
  },
  "references-count": 25,
  "journal-issue": {
    "issue": "5163",
    "published-print": {
      "date-parts": [
        [
          1994,
          5,
          27
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1126/science.264.5163.1297"
  ],
  "URL": "http://dx.doi.org/10.1126/science.264.5163.1297",
  "relation": {},
  "ISSN": [
    "0036-8075",
    "1095-9203"
  ],
  "subject": [],
  "container-title-short": "Science",
  "published": {
    "date-parts": [
      [
        1994,
        5,
        27
      ]
    ]
  }
}