An initial study of time complexity in infinite-domain constraint satisfaction

摘要

The constraint satisfaction problem (CSP) is a widely studied problem with numerous applications in computer science and artificial intelligence. For infinite-domain CSPs, there are many results separating tractable and NP-hard cases while upper and lower bounds on the time complexity of hard cases are virtually unexplored. Hence, we initiate a study of the worst-case time complexity of such CSPs. We analyze backtracking algorithms and determine upper bounds on their time complexity. We present asymptotically faster algorithms based on enumeration techniques and we show that these algorithms are applicable to well-studied problems in, for instance, temporal reasoning. Finally, we prove non-trivial lower bounds applicable to many interesting CSPs, under the assumption that certain complexity-theoretic assumptions hold. The gap between upper and lower bounds is in many cases surprisingly small, which suggests that our upper bounds cannot be significantly improved.