From k-SAT to k-CSP: Two Generalized Algorithms

Partially supported by the National 973 Program of China (Grant No. 2005CB321901). Preprint submitted to Elsevier 29 January 2018 with bounded clause length k (k-SAT) can be classified into three styles: DPLL-like, PPSZ-like and Local Search [2], with local search algorithms having already been generalized to CSP with bounded constraint arity k (k-CSP) [5]. We generalize a DPLL-like algorithm in its simplest form and a PPSZlike algorithm [4] from k-SAT to k-CSP. As far as we know, this is the first attempt to use PPSZ-like strategy to solve k-CSP, and before little work has been focused on the DPLL-like or PPSZ-like strategies for k-CSP.