Options
Algebraic and algorithmic synergies between promise and infinite-domain CSPs
Publikationstyp
Conference Paper
Date Issued
2025-06
Sprache
English
Author(s)
Start Page
357
End Page
371
Citation
40th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2025
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
IEEE
ISBN
979-8-3315-5464-4
We establish a framework that allows us to transfer results between some constraint satisfaction problems with infinite templates and promise constraint satisfaction problems. On the one hand, we obtain new algebraic results for infinite-domain CSPs giving new criteria for NP-hardness. On the other hand, we show the existence of promise CSPs with finite templates that reduce naturally to tractable infinite-domain CSPs in the scope of the Bodirsky-Pinsker conjecture, but that are not finitely tractable, thereby showing a non-trivial connection between those two fields of research. In an important part of our proof, we also obtain uniform polynomial-time algorithms solving temporal constraint satisfaction problems.
Subjects
constraint satisfaction
promise problems
temporal reasoning
uniform algorithm
DDC Class
004: Computer Sciences