Note to users. If you're seeing this message, it means that your browser cannot find this page's style/presentation instructions -- or possibly that you are using a browser that does not support current Web standards. Find out more about why this message is appearing, and what you can do to make your experience of our site the best it can be.
University of Rostock

Site Tools

  • AAAS
  • Subscribe
  • Feedback

Site Search

Search Advanced

Science 27 May 1994:
Vol. 264. no. 5163, pp. 1297 - 1301
DOI: 10.1126/science.264.5163.1297
Prev | Table of Contents | Next

Articles

Critical Behavior in the Satisfiability of Random Boolean Expressions

Scott Kirkpatrick 1 and Bart Selman 1

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

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.

Submitted on November 30, 1993
Accepted on March 23, 1994


THIS ARTICLE HAS BEEN CITED BY OTHER ARTICLES:
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem.
E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda (2001)
Science 292, 472-475
   Abstract »    Full Text »


ADVERTISEMENT
Click Me!

ADVERTISEMENT
Click Me!

To Advertise     Find Products

Science. ISSN 0036-8075 (print), 1095-9203 (online)