Random Walk Algorithms for SAT and Constraint Satisfaction Problems

Schöning [25] presents a simple yet elegant randomized algorithm for (d, k)-CSP problems with a running time of (d(k − 1)/k)n poly(n). Here, d is the number of colours, k is the size of the constraints and n is the number of variables. In the context of the derandomization of Schöning’s algorithm by Dantsin et al. [3], Scheder [24] gave an improvement by defining a graph structure on the set of d colours, the search graph. In this thesis we consider the same modification for the randomized version of Schöning’s algorithm and show that it does not give a better running time. More precisely, we show that for any search graph satisfying the symmetry property of distance-regularity, the running time is (d(k − 1)/k)n poly(n), the same running time as the original algorithm