The Ppsz Algorithm For Constraint Satisfaction Problems On More Than Two Colors

The PPSZ algorithm (Paturi et al., FOCS 1998) is the fastest known algorithm for k-SAT. We show how to extend the algorithm and its analysis to (d, k)-Clause Satisfaction Problems where each variable ranges over d different values. Given an input instance with a unique satisfying assignment, the resulting algorithm is the fastest known algorithm for ( d, k)-CSP except when ( d, k) is ( 3, 2) or ( 4, 2). For the general case of multiple satisfying assignments, our algorithm is the fastest known for all k >= 4.