Upper and Lower Bounds on the Time Complexity of Infinite-domain CSPs
2015 (English)In: Principles and Practice of Constraint Programming - 21st International Conference, CP 2015, Cork, Ireland, August 31 - September 4, 2015, Proceedings, Springer Berlin/Heidelberg, 2015, Vol. 9255, 183-199 p.Conference paper (Refereed)
The constraint satisfaction problem (CSP) is a widely studied problem with numerous applications in computer science. For infinite-domain CSPs, there are many results separating tractable and NP-hard cases while upper bounds on the time complexity of hard cases are virtually unexplored. Hence, we initiate a study of the worst-case time cmplexity of such CSPs. We analyse backtracking algorithms and show that they can be improved by exploiting sparsification. We present even faster algorithms based on enumerating finite structures. Last, we prove non-trivial lower bounds applicable to many interesting CSPs, under the assumption that the strong exponential-time hypothesis is true.
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2015. Vol. 9255, 183-199 p.
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 9255
Computer and Information Science Computer Science
IdentifiersURN: urn:nbn:se:liu:diva-123120DOI: 10.1007/978-3-319-23219-5_14ISI: 000364707100014ISBN: 978-3-319-23218-8OAI: oai:DiVA.org:liu-123120DiVA: diva2:876689
21st International Conference on Principles and Practice of Constraint Programming (CP-2015)