BACKTRACKING AND RANDOM CONSTRAINT SATISFACTION

The average running time used by backtracking on random constraint sat isfaction problems is studied. This time is polynomial when the ratio of constraints to variables is large, and it is exponential when the r atio is small. When the number of variables goes to infinity, whether the average time is exponential or polynomial depends on the number of variables per constraint, the number of values per variable, and the probability that a random setting of variables satisfies a constraint. A method for computing the curve that separates polynomial from expon ential time and several methods for approximating the curve are given. The version of backtracking studied finds all solutions to a problem, so the running time is exponential when the number of solutions per p roblem is exponential. For small values of the probability, the curve that separates exponential and polynomial average running time coincid es with the curve that separates an exponential average number of solu tions from a polynomial number. For larger probabilities the two curve s diverge. Random problems similar to those that arise in understandin g line drawings with shadows require a time that is mildly exponential when they are solved by simple backtracking. Slightly more sophistica ted algorithms (such as constraint propagation combined with backtrack ing) should be able to solve these rapidly.