CRITICAL-BEHAVIOR IN THE SATISFIABILITY OF RANDOM BOOLEAN EXPRESSIONS

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.