Average-Case Analysis
Goldberg (1979) reported very good performance of Davis-Putnam (DP) procedure on random instances.
But distribution favored easy instances. (Franco and Paull 1983)
Problem: Many randomly generated SAT problems are surprisingly easy.
Goldberg used variable-clause-length model:
For each clause, pick each literal with probability p.