AVERAGE-CASE RESULTS FOR SATISFIABILITY ALGORITHMS UNDER THE RANDOM-CLAUSE-WIDTH MODEL

In the probabilistic analysis of algorithms for the Satisfiability pro blem, the random-clause-width model is one of the most popular for gen erating random formulas. This model is parameterized and it is not dif ficult to show that virtually the entire parameter space is covered by a collection of polynomial time algorithms that find solutions to ran dom formulas with probability tending to 1 as formula size increases. But finding a collection of polynomial average time algorithms that co ver the parameter space has proved much harder and such results have s panned approximately ten years. However, it can now be said that virtu ally the entire parameter space is covered by polynomial average time algorithms. This paper relates dominant, exploitable properties of ran dom formulas over the parameter space to mechanisms of polynomial aver age time algorithms. The probabilistic discussion of such properties i s new; main average-case results over the last ten years are reviewed.