Abstract
An instance of the constraint satisfaction problem with $n$ variables over a domain of $d$ values can be solved by brute-force in $d^n$ steps (omitting a polynomial factor). In this talk, we investigate the existence of subexponential-time algorithms, that is, algorithms running in $d^{o(n)}$ steps, for various natural restrictions of the constraint satisfaction problem. We discuss both the constraint satisfaction problem in which all the constraints are given extensionally as tables, and that in which all the constraints are given intensionally in the form of global constraints. We provide tight characterizations of the subexponential-time complexity of the aforementioned problems with respect to several natural structural parameters, which allows us to draw a detailed landscape of the subexponential-time complexity of the constraint satisfaction problem. Our analysis provides results indicating whether and when one can significantly improve on the brute-force search approach for solving the constraint satisfaction problem.