×

The wonderland of reflections. (English) Zbl 1397.08002

The paper is devoted to the study of the well-known notion of CSPs (constraint satisfaction problems). For a comparison of the complexity of relational structures \(\mathbb A\), \(\mathbb B\), the following reductions expressing that \(\mathrm{CSP}(\mathbb B)\) is at most hard as \(\mathrm{CSP}(\mathbb A)\) are used:
(a)
\(\mathbb B\) is pp-interpretable in \(\mathbb A\),
(b)
\(\mathbb B\) is homomorphically equivalent to \(\mathbb A\),
(c)
\(\mathbb A\) is a core and \(\mathbb B\) is obtained from \(\mathbb A\) by adding a singleton unary relation.
The authors prove a theorem giving a criterion on the structure of the polymorphism clone \(\mathcal A\) of \(\mathbb A\), rather than \(\mathcal B\), which divides NP-hard from polynomial-time solvable CPSs for all finite structures \(\mathbb A\), without necessity to consider their cores. For this purpose, an operator \(\operatorname{E}\) referred to as reflection acting on on function clones is defined: if \(\mathcal A\) is a function clone then \(\operatorname{E}(\mathcal A)\) yields all function clones obtained from \(\mathcal A\) by adding functions to it.
Furthermore, a generalization for infinite (countable) categorical structures is dealt with, together with some topological considerations.

MSC:

08A40 Operations and polynomials in algebraic structures, primal algebras
08A70 Applications of universal algebra in computer science
03C05 Equational classes, universal algebra in model theory
03C15 Model theory of denumerable and separable structures
03C35 Categoricity and completeness of theories
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Barto, L., The constraint satisfaction problem and universal algebra, Bull. Symb. Log., 2015, 319-337, (2015) · Zbl 1336.68113
[2] Barto, L.; Kozik, M., Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem, Log. Methods Comput. Sci., 8, 27, (2012) · Zbl 1239.08002
[3] Barto, L.; Kozik, M., Constraint satisfaction problems solvable by local consistency methods, J. ACM, 61, 19, (2014) · Zbl 1295.68126
[4] Bentz, W.; Sequeira, L., Taylor’s modularity conjecture holds for linear idempotent varieties, Algebra Universalis, 2014, 101-107, (2014) · Zbl 1303.08006
[5] C. Bergman, Universal Algebra: Fundamentals and Selected Topics, Pure and Applied Mathematics (Boca Raton), Vol. 301, CRC Press, Boca Raton, FL, 2012. · Zbl 1229.08001
[6] Birkhoff, G., On the structure of abstract algebras, Mathematical Proceedings of the Cambridge Philosophical Society, 1935, 433-454, (1935) · JFM 61.1026.07
[7] Bodirsky, M., Cores of countably categorical structures, Log. Methods Comput. Sci., 3, 16, (2007) · Zbl 1128.03021
[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. · Zbl 1261.03118
[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. · Zbl 1327.03008
[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. · Zbl 1287.68068
[11] Bodirsky, M.; Kára, J., The complexity of temporal constraint satisfaction problems, J. ACM, 57, 41, (2010) · Zbl 1327.68125
[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. · Zbl 1440.68111
[13] Bodirsky, M.; Nešetřil, J., Constraint satisfaction with countable homogeneous templates, J. Logic Comput., 2006, 359-373, (2006) · Zbl 1113.03026
[14] Bodirsky, M.; Pinsker, M., Reducts of Ramsey structures, Model theoretic methods in finite combinatorics, Contemp. Math., 558, 489-519, (2011) · Zbl 1261.03118
[15] Bodirsky, M.; Pinsker, M., Schaefer’s theorem for graphs, J. ACM, 62, 52, (2015) · Zbl 1333.05194
[16] Bodirsky, M.; Pinsker, M., Topological Birkhoff, Trans. Amer.Math. Soc., 2015, 2527-2549, (2015) · Zbl 1375.03032
[17] Bodirsky, M.; Pinsker, M.; Pongrácz, A., Projective clone homomorphisms, (2014)
[18] Bodirsky, M.; Pinsker, M.; Pongrácz, A., Reconstructing the topology of clones, Trans. Amer. Math. Soc., 2017, 3707-3740, (2017) · Zbl 1377.03021
[19] Bodirsky, M.; Pinsker, M.; Tsankov, T., Decidability of definability, J. Symbolic Logic, 2013, 1036-1054, (2013) · Zbl 1327.03008
[20] Bulatov, A.; Jeavons, P.; Krokhin, A., Classifying the complexity of constraints using finite algebras, SIAM J. Comput., 2005, 720-742, (2005) · Zbl 1071.08002
[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. · Zbl 0478.08001
[22] Feder, T.; Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory, SIAM J. Comput., 1999, 57-104, (1999) · Zbl 0914.68075
[23] García, O. C.; Taylor, W., The lattice of interpretability types of varieties, Mem.Amer. Math. Soc., 50, 125, (1984) · Zbl 0559.08003
[24] Gehrke, M.; Pinsker, M., Uniform Birkhoff, (2016) · Zbl 06825569
[25] Hagemann, J.; Mitschke, A., On n-permutable congruences, Algebra Universalis, 1973, 8-12, (1973) · Zbl 0273.08001
[26] W. Hodges, A shorter model theory, Cambridge University Press, Cambridge, 1997. · Zbl 0873.03036
[27] Kearnes, K., P. marković and R. mckenzie, Optimal strong Mal’cev conditions for omitting type 1 in locally finite varieties, Algebra Universalis, 2014, 91-100, (2014)
[28] Kearnes, K. A.; T. Tschantz, S., Automorphism groups of squares and of free algebras, Internat. J. Algebra Comput., 2007, 461-505, (2007) · Zbl 1158.08003
[29] Larose, B.; Zádori, L., Bounded width problems and algebras, Algebra Universalis, 2007, 439-466, (2007) · Zbl 1120.08002
[30] Neumann, W. D., On malcev conditions, J. Austral. Math. Soc., 1974, 376-384, (1974) · Zbl 0294.08004
[31] M. Pinsker, Algebraic and model theoretic methods in constraint satisfaction, arXiv:1507.00931 (2015).
[32] L. Sequeira, Maltsev filters, 2001, Thesis (Ph.D.)-University of Lisbon, Portugal.
[33] Siggers, M. H., A strong mal’cev condition for locally finite varieties omitting the unary type, Algebra Universalis, 2010, 15-20, (2010) · Zbl 1216.08002
[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. · Zbl 0603.08004
[35] Taylor, W., Varieties obeying homotopy laws, Canad. J. Math., 1977, 498-527, (1977) · Zbl 0357.08004
[36] S. T. Tschantz, Congruence permutability is join prime, unpublished (1996).
[37] Valeriote, M.; Willard, R., Idempotent n-permutable varieties, Bull. Lond. Math. Soc., 2014, 870-880, (2014) · Zbl 1303.08005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.