Average-Case Analysis
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.