Critical Behavior in the Satisfiability of Random Boolean Expressions

See allHide authors and affiliations

Science  27 May 1994:
Vol. 264, Issue 5163, pp. 1297-1301
DOI: 10.1126/science.264.5163.1297


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.