Determining the satisfiability of randomly generated Boolean expressio
ns with k variables per clause is a popular test for the performance o
f search algorithms ih artificial intelligence and computer science. I
t 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 t
han 1, the formulas are almost never satisfiable. Similar sharp thresh
old behavior is observed for higher values of k. Finite-size scaling,
a method from statistical physics, can be used to characterize size-de
pendent effects near the threshold. A relationship can be drawn betwee
n thresholds and computational complexity.