title: Critical behavior in the satisfiability of random boolean expressions.
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.
authors.forename: S
authors.initials: S
authors.lastname: Kirkpatrick
authors.forename: B
authors.initials: B
authors.lastname: Selman