Skip to main content
SpringerLink
Log in

The wonderland of reflections

  • Published:
Israel Journal of Mathematics Aims and scope Submit manuscript

Abstract

A fundamental fact for the algebraic theory of constraint satisfaction problems (CSPs) over a fixed template is that pp-interpretations between at most countable ω-categorical relational structures have two algebraic counterparts for their polymorphism clones: a semantic one via the standard algebraic operators H, S, P, and a syntactic one via clone homomorphisms (capturing identities). We provide a similar characterization which incorporates all relational constructions relevant for CSPs, that is, homomorphic equivalence and adding singletons to cores in addition to ppinterpretations. For the semantic part we introduce a new construction, called reflection, and for the syntactic part we find an appropriate weakening of clone homomorphisms, called h1 clone homomorphisms (capturing identities of height 1).

As a consequence, the complexity of the CSP of an at most countable ω-categorical structure depends only on the identities of height 1 satisfied in its polymorphism clone as well as the natural uniformity thereon. This allows us in turn to formulate a new elegant dichotomy conjecture for the CSPs of reducts of finitely bounded homogeneous structures.

Finally, we reveal a close connection between h1 clone homomorphisms and the notion of compatibility with projections used in the study of the lattice of interpretability types of varieties.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. L. Barto, The constraint satisfaction problem and universal algebra, Bull. Symb. Log. 2015 (2015), 319᾿37.

    Article  MathSciNet  MATH  Google Scholar 

  2. L. Barto and M. Kozik, Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem, Log. Methods Comput. Sci. 8 (2012), paper 7, 27 pages.

    MathSciNet  MATH  Google Scholar 

  3. L. Barto and M. Kozik, Constraint satisfaction problems solvable by local consistency methods, J. ACM 61 (2014), article 3, 19 pages.

    MathSciNet  MATH  Google Scholar 

  4. W. Bentz and L. Sequeira, Taylor’s modularity conjecture holds for linear idempotent varieties, Algebra Universalis 2014 (2014), 101᾿07.

    Article  MathSciNet  MATH  Google Scholar 

  5. C. Bergman, Universal Algebra: Fundamentals and Selected Topics, Pure and Applied Mathematics (Boca Raton), Vol. 301, CRC Press, Boca Raton, FL, 2012.

  6. G. Birkhoff, On the structure of abstract algebras, Mathematical Proceedings of the Cambridge Philosophical Society 1935 (1935), 433᾿54.

    Article  MATH  Google Scholar 

  7. M. Bodirsky, Cores of countably categorical structures, Log. Methods Comput. Sci. 3 (2007), paper 2, 16 pages.

    MathSciNet  MATH  Google Scholar 

  8. M. Bodirsky, Constraint satisfaction problems with infinite templates, in Complexity of Constraints: An Overview of Current Research Themes, Lecture Notes in Comput. Sci., Vol. 5250, Springer Berlin Heidelberg, 2008, pp. 196᾿28.

  9. M. Bodirsky, Complexity classification in infinite-domain constraint satisfaction, Mémoire d’habilitation à diriger des recherches, Université Diderot–Paris 7 (2012), Available at arXiv:1201.0856.

  10. M. Bodirsky, V. Dalmau, B. Martin and M. Pinsker, Distance constraint satisfaction problems, in Mathematical foundations of computer science 2010, Lecture Notes in Comput. Sci., Vol. 6281, Springer, Berlin, 2010, pp. 162᾿73.

  11. M. Bodirsky and J. Kára, The complexity of temporal constraint satisfaction problems, J. ACM 57 (2010), article 9, 41 pages.

    MathSciNet  MATH  Google Scholar 

  12. M. Bodirsky, B. Martin and A. Mottet, Constraint satisfaction problems over the integers with successor, in Automata, languages, and programming. Part I, Lecture Notes in Comput. Sci., Vol. 9134, Springer, Heidelberg, 2015, pp. 256᾿67.

  13. M. Bodirsky and J. Nešetřil, Constraint satisfaction with countable homogeneous templates, J. Logic Comput. 2006 (2006), 359᾿73.

    Article  MathSciNet  MATH  Google Scholar 

  14. M. Bodirsky and M. Pinsker, Reducts of Ramsey structures, in Model theoretic methods in finite combinatorics, Contemp. Math., Vol. 558, Amer. Math. Soc., Providence, RI, 2011, pp. 489᾿19.

    Article  MathSciNet  MATH  Google Scholar 

  15. M. Bodirsky and M. Pinsker, Schaefer’s theorem for graphs, J. ACM 62 (2015), article 19, 52 pages.

    MathSciNet  MATH  Google Scholar 

  16. M. Bodirsky and M. Pinsker, Topological Birkhoff, Trans. Amer.Math. Soc. 2015 (2015), 2527᾿549.

    MathSciNet  MATH  Google Scholar 

  17. M. Bodirsky, M. Pinsker and A. Pongrácz, Projective clone homomorphisms, Journal of Symbolic Logic, to appear. Preprint available arXiv:1409.4601 (2014).

    Google Scholar 

  18. M. Bodirsky, M. Pinsker and A. Pongrácz, Reconstructing the topology of clones, Trans. Amer. Math. Soc. 2017 (2017), 3707᾿740.

    Article  MathSciNet  MATH  Google Scholar 

  19. M. Bodirsky, M. Pinsker and T. Tsankov, Decidability of definability, J. Symbolic Logic 2013 (2013), 1036᾿054.

    Article  MathSciNet  MATH  Google Scholar 

  20. A. Bulatov, P. Jeavons and A. Krokhin, Classifying the complexity of constraints using finite algebras, SIAM J. Comput. 2005 (2005), 720᾿42.

    Article  MathSciNet  MATH  Google Scholar 

  21. S. N. Burris and H. P. Sankappanavar, A course in universal algebra, Graduate Texts in Mathematics, Vol. 78, Springer-Verlag, New York-Berlin, 1981.

  22. 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. 1999 (1999), 57᾿04.

    MathSciNet  MATH  Google Scholar 

  23. O. C. García and W. Taylor, The lattice of interpretability types of varieties, Mem.Amer. Math. Soc. 50 (1984), v+125.

    MathSciNet  MATH  Google Scholar 

  24. M. Gehrke and M. Pinsker, Uniform Birkhoff, Journal of Pure and Applied Algebra, in press (2016).

    Google Scholar 

  25. J. Hagemann and A. Mitschke, On n-permutable congruences, Algebra Universalis 1973 (1973), 8᾿2.

    Article  MathSciNet  MATH  Google Scholar 

  26. W. Hodges, A shorter model theory, Cambridge University Press, Cambridge, 1997.

    MATH  Google Scholar 

  27. K. Kearnes, P. Marković and R. McKenzie, Optimal strong Mal’cev conditions for omitting type 1 in locally finite varieties, Algebra Universalis 2014 (2014), 91᾿00.

    MathSciNet  Google Scholar 

  28. K. A. Kearnes and S. T. Tschantz, Automorphism groups of squares and of free algebras, Internat. J. Algebra Comput. 2007 (2007), 461᾿05.

    Article  MathSciNet  MATH  Google Scholar 

  29. B. Larose and L. Zádori, Bounded width problems and algebras, Algebra Universalis 2007 (2007), 439᾿66.

    Article  MathSciNet  MATH  Google Scholar 

  30. W. D. Neumann, On Malcev conditions, J. Austral. Math. Soc. 1974 (1974), 376᾿84. Collection of articles dedicated to the memory of Hanna Neumann, VII.

    Article  MathSciNet  MATH  Google Scholar 

  31. M. Pinsker, Algebraic and model theoretic methods in constraint satisfaction, arXiv:1507.00931 (2015).

    Google Scholar 

  32. L. Sequeira, Maltsev filters, 2001, Thesis (Ph.D.)–University of Lisbon, Portugal.

    Google Scholar 

  33. M. H. Siggers, A strong Mal’cev condition for locally finite varieties omitting the unary type, Algebra Universalis 2010 (2010), 15᾿0.

    Article  MathSciNet  MATH  Google Scholar 

  34. Á. Szendrei, Clones in universal algebra, Séminaire de Mathématiques Supérieures [Seminar on Higher Mathematics], Vol. 99, Presses de l’Université de Montréal, Montreal, QC, 1986.

  35. W. Taylor, Varieties obeying homotopy laws, Canad. J. Math. 1977 (1977), 498᾿27.

    Article  MathSciNet  MATH  Google Scholar 

  36. S. T. Tschantz, Congruence permutability is join prime, unpublished (1996).

    Google Scholar 

  37. M. Valeriote and R. Willard, Idempotent n-permutable varieties, Bull. Lond. Math. Soc. 2014 (2014), 870᾿80.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Algebra, MFF UK, Sokolovska 83, 186 00, Praha 8, Czech Republic

    Libor Barto, Jakub Opršal & Michael Pinsker

Authors
  1. Libor Barto
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jakub Opršal
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michael Pinsker
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Libor Barto.

Additional information

Libor Barto and Jakub Opršal were supported by the Grant Agency of the Czech Republic, grant GAČR 13-01832S. Michael Pinsker has been funded through project P27600 of the Austrian Science Fund (FWF).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Barto, L., Opršal, J. & Pinsker, M. The wonderland of reflections. Isr. J. Math. 223, 363–398 (2018). https://doi.org/10.1007/s11856-017-1621-9

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11856-017-1621-9

Search

Navigation