Options
Smooth approximations : an algebraic approach to CSPs over finitely bounded homogeneous structures
Publikationstyp
Journal Article
Date Issued
2024-10-05
Sprache
English
Journal
Volume
71
Issue
5
Article Number
36
Citation
Journal of the ACM 71 (5): 36 (2024)
Publisher DOI
Scopus ID
Publisher
ACM
ISSN
00045411
We introduce the novel machinery of smooth approximations to provide a systematic algebraic approach to the complexity of CSPs over finitely bounded homogeneous structures. We apply smooth approximations to confirm the CSP dichotomy conjecture for first-order reducts of the random tournament and to give new short proofs of the conjecture for various homogeneous graphs including the random graph (STOC'11, ICALP'16, JACM 2015, SICOMP 2019), and for expansions of the order of the rationals (STOC'08, JACM 2009). Apart from obtaining these dichotomy results, we show how our new proof technique allows one to unify and significantly simplify the previous results from the literature. For all but the last structure, we moreover characterize for the first time those CSPs that are solvable by local consistency methods, again using the same machinery.
Subjects
complexity dichotomy
Constraint Satisfaction Problem
finitely bounded
homogeneous
loop lemma
\omega-categorical
polymorphism
standard compactness argument
DDC Class
004: Computer Sciences
510: Mathematics