Analysis of Backtracking on Random k-SAT
Ke Xü · Chinese Journal of Computers · 2000
By analyzing the expected number of nodes in a search tree, the average running time used by the backtracking algorithm on random k SAT is studies in this paper. The results show that the expected number of nodes required for finding all solutions or proving that no solution exists becomes exponentially large as n (the number of variables) grows. In addition, as r (the ratio of the number of clauses to the number of variables) increases, random k SAT instances get easier and easier to solve, and the base for the expected number of nodes that is exponential in n tends to 1 as r approaches infinity. Therefore, although the average running time used by the backtracking algorithm on random k SAT is exponential, many SAT instances will be very easy to solve when r is sufficiently large.