World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures

https://doi.org/10.1142/S0219061319500107Cited by:15 (Source: Crossref)

There exist two conjectures for constraint satisfaction problems (CSPs) of reducts of finitely bounded homogeneous structures: the first one states that tractability of the CSP of such a structure is, when the structure is a model-complete core, equivalent to its polymorphism clone satisfying a certain nontrivial linear identity modulo outer embeddings. The second conjecture, challenging the approach via model-complete cores by reflections, states that tractability is equivalent to the linear identities (without outer embeddings) satisfied by its polymorphisms clone, together with the natural uniformity on it, being nontrivial. We prove that the identities satisfied in the polymorphism clone of a structure allow for conclusions about the orbit growth of its automorphism group, and apply this to show that the two conjectures are equivalent. We contrast this with a counterexample showing that ω-categoricity alone is insufficient to imply the equivalence of the two conditions above in a model-complete core. Taking another approach, we then show how the Ramsey property of a homogeneous structure can be utilized for obtaining a similar equivalence under different conditions. We then prove that any polymorphism of sufficiently large arity which is totally symmetric modulo outer embeddings of a finitely bounded structure can be turned into a nontrivial system of linear identities, and obtain nontrivial linear identities for all tractable cases of reducts of the rational order, the random graph, and the random poset. Finally, we provide a new and short proof, in the language of monoids, of the theorem stating that every ω-categorical structure is homomorphically equivalent to a model-complete core.

AMSC: 03C05, 03C40, 08B05, 68Q17, 20B27

References

  • 1. L. Barto, J. Opršal and M. Pinsker, The wonderland of reflections, Israel J. Math. 223(1) (2018) 363–398. Crossref, Web of ScienceGoogle Scholar
  • 2. L. Barto and M. Pinsker, Topology is irrelevant, Preprint available from the authors’ websites, 2018. Google Scholar
  • 3. C. Bergman, Universal Algebra: Fundamentals and Selected Topics, Pure and Applied Mathematics (Taylor and Francis, 2011). CrossrefGoogle Scholar
  • 4. M. Bodirsky, Complexity classification in infinite-domain constraint satisfaction, Mémoire d’habilitation à diriger des recherches, Université Diderot — Paris 7 (2012), arXiv:1201.0856. Google Scholar
  • 5. M. Bodirsky, Cores of countably categorical structures, Logical Methods Comput. Sci. 3(1) (2007) 1–16. Crossref, Web of ScienceGoogle Scholar
  • 6. M. Bodirsky, D. Evans, M. Kompatscher and M. Pinsker, A counterexample to the reconstruction of ω-categorical structures from their endomorphism monoids, Israel J. Math. 224(1) (2018) 57–82. Crossref, Web of ScienceGoogle Scholar
  • 7. M. Bodirsky and M. Grohe, Non-dichotomies in constraint satisfaction complexity, in Proc. Int. Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science (Springer Verlag, 2008), pp. 184–196. CrossrefGoogle Scholar
  • 8. M. Bodirsky, M. Hils and B. Martin, On the scope of the universal-algebraic approach to constraint satisfaction, Logical Methods Comput. Sci. (LMCS) 8(3:13) (2012). Web of ScienceGoogle Scholar
  • 9. M. Bodirsky and M. Junker, 0-categorical structures: Interpretations and endomorphisms, Algebra Universalis 64(3–4) (2011) 403–417. Crossref, Web of ScienceGoogle Scholar
  • 10. M. Bodirsky and J. Kára, The complexity of equality constraint languages, Theory Comput. Syst. 3(2) (2008) 136–158. Crossref, Web of ScienceGoogle Scholar
  • 11. M. Bodirsky and J. Kára, The complexity of temporal constraint satisfaction problems, J. ACM 57(2) (2009) 1–41. Crossref, Web of ScienceGoogle Scholar
  • 12. M. Bodirsky and M. Pinsker, Reducts of Ramsey structures, AMS Contemporary Mathematics (Model Theoretic Methods in Finite Combinatorics), Vol. 558 (2011), pp. 489–519. CrossrefGoogle Scholar
  • 13. M. Bodirsky and M. Pinsker, Schaefer’s theorem for graphs, J. ACM 62(3) (2015) 52, Article No. 19. Crossref, Web of ScienceGoogle Scholar
  • 14. M. Bodirsky and M. Pinsker, Topological Birkhoff, Trans. Amer. Math. Soc. 367 (2015) 2527–2549. Crossref, Web of ScienceGoogle Scholar
  • 15. L. Barto and M. Pinsker, The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems, in Proc. 31th Annual IEEE Symp. on Logic in Computer Science — LICS’16 (2016), pp. 615–622, arXiv:1602.04353. CrossrefGoogle Scholar
  • 16. M. Bodirsky and M. Pinsker, Canonical functions: A new proof via topological dynamics, preprint (2016), arXiv:1610.09660. Google Scholar
  • 17. M. Bodirsky, M. Pinsker and A. Pongrácz, Projective clone homomorphisms, J. Symbolic Logic, to appear. Preprint arXiv:1409.4601. Google Scholar
  • 18. M. Bodirsky, M. Pinsker and A. Pongrácz, Reconstructing the topology of clones, Trans. Amer. Math. Soc. 369 (2017) 3707–3740. Crossref, Web of ScienceGoogle Scholar
  • 19. A. A. Bulatov, A dichotomy theorem for nonuniform CSPs, in 58th IEEE Annual Symp. on Foundations of Computer Science, FOCS 2017 (2017), pp. 319–330. CrossrefGoogle Scholar
  • 20. S. N. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Graduate Texts in Mathematics, Vol. 78 (Springer Verlag, New York, 1981). CrossrefGoogle Scholar
  • 21. P. J. Cameron, Oligomorphic Permutation Groups (Cambridge University Press, Cambridge, 1990). CrossrefGoogle Scholar
  • 22. R. Fraïssé, Sur l’extension aux relations de quelques propriétés des ordres, Ann. Sci. École Norm. Sup. 71 (1954) 363–388. CrossrefGoogle Scholar
  • 23. R. Fraïssé, Theory of Relations (Elsevier Science Ltd/North-Holland, 1986). Google Scholar
  • 24. T. Feder and M. Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory, SIAM J. Comput. 28 (1999) 57–104. Crossref, Web of ScienceGoogle Scholar
  • 25. M. Gehrke and M. Pinsker, Uniform Birkhoff, J. Pure Appl. Algebra 222(5) (2018) 1242–1250. Crossref, Web of ScienceGoogle Scholar
  • 26. W. Hodges, A Shorter Model Theory (Cambridge University Press, Cambridge, 1997). Google Scholar
  • 27. A. Kechris, V. Pestov and S. Todorcevic, Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups, Geom. Funct. Anal. 15(1) (2005) 106–189. Crossref, Web of ScienceGoogle Scholar
  • 28. M. Kompatscher and T. V. Pham, A complexity dichotomy for poset constraint satisfaction, in 34th Symp. Theoretical Aspects of Computer Science (STACS 2017), Vol. 66 (2017), pp. 47:1–47:12. Google Scholar
  • 29. W. Kubiś, Fraïssé sequences: Category-theoretic approach to universal homogeneous structures, Ann. Pure Appl. Logic 165 (2014) 1755–1811. Crossref, Web of ScienceGoogle Scholar
  • 30. D. Macpherson, A survey of homogeneous structures, Discrete Math. 311(15) (2011) 1599–1634. Crossref, Web of ScienceGoogle Scholar
  • 31. C. Pech and M. Pech, Towards a Ryll–Nardzewski-type theorem for weakly oligomorphic structures, Math. Log. Q. 62(1–2) (2016) 25–34. Crossref, Web of ScienceGoogle Scholar
  • 32. F. M. Schneider, A uniform Birkhoff theorem, 78(3) (2017) 337–354. Google Scholar
  • 33. S. Thomas, Reducts of the random graph, J. Symbolic Logic 56(1) (1991) 176–181. Crossref, Web of ScienceGoogle Scholar
  • 34. D. Zhuk, A proof of CSP dichotomy conjecture, in 58th IEEE Annual Symp. on Foundations of Computer Science, FOCS 2017 (2017), pp. 331–342. CrossrefGoogle Scholar