$\omega$-categorical structures avoiding height 1 identities
HTML articles powered by AMS MathViewer
- by Manuel Bodirsky, Antoine Mottet, Miroslav Olšák, Jakub Opršal, Michael Pinsker and Ross Willard PDF
- Trans. Amer. Math. Soc. 374 (2021), 327-350 Request permission
Corrigendum: Trans. Amer. Math. Soc. (to appear).
Abstract:
The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable if the model-complete core of the template has a pseudo-Siggers polymorphism, and is NP-complete otherwise.
One of the important questions related to the dichotomy conjecture is whether, similarly to the case of finite structures, the condition of having a pseudo-Siggers polymorphism can be replaced by the condition of having polymorphisms satisfying a fixed set of identities of height 1, i.e., identities which do not contain any nesting of functional symbols. We provide a negative answer to this question by constructing for each nontrivial set of height 1 identities a structure within the range of the conjecture whose polymorphisms do not satisfy these identities, but whose CSP is tractable nevertheless.
An equivalent formulation of the dichotomy conjecture characterizes tractability of the CSP via the local satisfaction of nontrivial height 1 identities by polymorphisms of the structure. We show that local satisfaction and global satisfaction of nontrivial height 1 identities differ for $\omega$-categorical structures with less than doubly exponential orbit growth, thereby resolving one of the main open problems in the algebraic theory of such structures.
References
- Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, J. Comput. System Sci. 54 (1997), no. 2, 317–331. 34th Annual Symposium on Foundations of Computer Science (Palo Alto, CA, 1993). MR 1462727, DOI 10.1006/jcss.1997.1472
- Libor Barto, Jakub Bulín, Andrei Krokhin, and Jakub Opršal. Algebraic approach to promise constraint satisfaction. arXiv:1811.00970v3, 2019.
- Manuel Bodirsky and Martin Grohe, Non-dichotomies in constraint satisfaction complexity, Automata, languages and programming. Part II, Lecture Notes in Comput. Sci., vol. 5126, Springer, Berlin, 2008, pp. 184–196. MR 2503587, DOI 10.1007/978-3-540-70583-3_{1}6
- Manuel Bodirsky and Peter Jonsson, A model-theoretic view on qualitative constraint reasoning, J. Artificial Intelligence Res. 58 (2017), 339–385. MR 3620326, DOI 10.1613/jair.5260
- Andrei Bulatov, Peter Jeavons, and Andrei Krokhin, Classifying the complexity of constraints using finite algebras, SIAM J. Comput. 34 (2005), no. 3, 720–742. MR 2137072, DOI 10.1137/S0097539700376676
- Manuel Bodirsky, Peter Jonsson, and Trung Van Pham, The complexity of phylogeny constraint satisfaction problems, ACM Trans. Comput. Log. 18 (2017), no. 3, Art. 23, 42. MR 3689377, DOI 10.1145/3105907
- Manuel Bodirsky and Jan Kára, The complexity of temporal constraint satisfaction problems, J. ACM 57 (2010), no. 2, Art. 9, 41. MR 2606084, DOI 10.1145/1667053.1667058
- Libor Barto and Marcin Kozik, Constraint satisfaction problems solvable by local consistency methods, J. ACM 61 (2014), no. 1, Art. 3, 19. MR 3167919, DOI 10.1145/2556646
- Libor Barto, Michael Kompatscher, Miroslav Olšák, Trung Van Pham, and Michael Pinsker, The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems, Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science – LICS’17, 2017.
- Libor Barto, Michael Kompatscher, Miroslav Olšák, Trung Van Pham, and Michael Pinsker, Equations in oligomorphic clones and the constraint satisfaction problem for $\omega$-categorical structures, J. Math. Log. 19 (2019), no. 2, 1950010, 31. MR 4014890, DOI 10.1142/S0219061319500107
- Libor Barto, Andrei Krokhin, and Ross Willard, Polymorphisms, and how to use them, The constraint satisfaction problem: complexity and approximability, Dagstuhl Follow-Ups, vol. 7, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017, pp. 1–44. MR 3631047
- Manuel Bodirsky, Florent Madelaine, and Antoine Mottet, A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP, LICS ’18—33rd Annual ACM/IEEE Symposium on Logic in Computer Science, ACM, New York, 2018, pp. [10 pp.]. MR 3883717, DOI 10.1145/3209108.3209156
- Manuel Bodirsky, Antoine Mottet, Miroslav Olšák, Jakub Opršal, Michael Pinsker, and Ross Willard. Topology is relevant (in the infinite-domain dichotomy conjecture for constraint satisfaction problems). In Proceedings of the Symposium on Logic in Computer Science – LICS’19, 2019. Preprint arXiv:1901.04237.
- Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz, Constraint satisfaction problems for reducts of homogeneous graphs, SIAM J. Comput. 48 (2019), no. 4, 1224–1264. MR 3982075, DOI 10.1137/16M1082974
- Manuel Bodirsky and Jaroslav Ne et il, Constraint satisfaction with countable homogeneous templates, J. Logic Comput. 16 (2006), no. 3, 359–373. MR 2239084, DOI 10.1093/logcom/exi083
- Manuel Bodirsky, Cores of countably categorical structures, Log. Methods Comput. Sci. 3 (2007), no. 1, 1:2, 16. MR 2295790, DOI 10.2168/LMCS-3(1:2)2007
- Manuel Bodirsky, Complexity classification in infinite-domain constraint satisfaction, Mémoire d’habilitation à diriger des recherches, Université Diderot – Paris 7. Available at arXiv:1201.0856, (2012).
- Libor Barto, Jakub Opršal, and Michael Pinsker, The wonderland of reflections, Israel J. Math. 223 (2018), no. 1, 363–398. MR 3773066, DOI 10.1007/s11856-017-1621-9
- Kirby A. Baker and Alden F. Pixley, Polynomial interpolation and the Chinese remainder theorem for algebraic systems, Math. Z. 143 (1975), no. 2, 165–174. MR 371782, DOI 10.1007/BF01187059
- Manuel Bodirsky and Michael Pinsker, Schaefer’s theorem for graphs, J. ACM 62 (2015), no. 3, Art. 19, 52. MR 3366998, DOI 10.1145/2764899
- Manuel Bodirsky and Michael Pinsker, Topological Birkhoff, Trans. Amer. Math. Soc. 367 (2015), no. 4, 2527–2549. MR 3301873, DOI 10.1090/S0002-9947-2014-05975-8
- Libor Barto and Michael Pinsker, The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems, Proceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science (LICS 2016), ACM, New York, 2016, pp. 8. MR 3776781, DOI 10.1145/2933575.2934544
- Libor Barto and Michael Pinsker, Topology is irrelevant (in a dichotomy conjecture for infinite domain constraint satisfaction problems), SIAM J. Comput. 49 (2020), no. 2, 365–393. MR 4080393, DOI 10.1137/18M1216213
- Manuel Bodirsky, Michael Pinsker, and András Pongrácz, Projective clone homomorphisms, Journal of Symbolic Logic. To appear.
- Andrei A. Bulatov, A dichotomy theorem for nonuniform CSPs, 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017, IEEE Computer Soc., Los Alamitos, CA, 2017, pp. 319–330. MR 3734240, DOI 10.1109/FOCS.2017.37
- Peter J. Cameron, Oligomorphic permutation groups, London Mathematical Society Lecture Note Series, vol. 152, Cambridge University Press, Cambridge, 1990. MR 1066691, DOI 10.1017/CBO9780511549809
- Gregory Cherlin, Saharon Shelah, and Niandong Shi, Universal graphs with forbidden subgraphs and algebraic closure, Adv. in Appl. Math. 22 (1999), no. 4, 454–491. MR 1683298, DOI 10.1006/aama.1998.0641
- M. El-Zahar and N. W. Sauer, The chromatic number of the product of two $4$-chromatic graphs is $4$, Combinatorica 5 (1985), no. 2, 121–126. MR 815577, DOI 10.1007/BF02579374
- Tomás Feder and Moshe Y. Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory, SIAM J. Comput. 28 (1999), no. 1, 57–104. MR 1630445, DOI 10.1137/S0097539794266766
- Mai Gehrke and Michael Pinsker, Uniform Birkhoff, J. Pure Appl. Algebra 222 (2018), no. 5, 1242–1250. MR 3742227, DOI 10.1016/j.jpaa.2017.06.016
- David Hobby and Ralph McKenzie, The structure of finite algebras, Contemporary Mathematics, vol. 76, American Mathematical Society, Providence, RI, 1988. MR 958685, DOI 10.1090/conm/076
- Jan Hubička and Jaroslav Ne et il, Homomorphism and embedding universal structures for restricted classes, J. Mult.-Valued Logic Soft Comput. 27 (2016), no. 2-3, 229–253. MR 3532466
- Wilfrid Hodges, A shorter model theory, Cambridge University Press, Cambridge, 1997. MR 1462612
- Bjarni Jónsson, Algebras whose congruence lattices are distributive, Math. Scand. 21 (1967), 110–121 (1968). MR 237402, DOI 10.7146/math.scand.a-10850
- Michael Kompatscher and Trung Van Pham, A complexity dichotomy for poset constraint satisfaction, 34th Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 66, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017, pp. Art. No. 47, 12. MR 3655374
- Miroslav Olšák, The weakest nontrivial idempotent equations, Bull. Lond. Math. Soc. 49 (2017), no. 6, 1028–1047. MR 3743486, DOI 10.1112/blms.12097
- Yaroslav Shitov, Counterexamples to Hedetniemi’s conjecture, Ann. of Math. (2) 190 (2019), no. 2, 663–667. MR 3997132, DOI 10.4007/annals.2019.190.2.6
- Mark H. Siggers, A strong Mal’cev condition for locally finite varieties omitting the unary type, Algebra Universalis 64 (2010), no. 1-2, 15–20. MR 2745482, DOI 10.1007/s00012-010-0082-3
- Walter Taylor, Some very weak identities, Algebra Universalis 25 (1988), no. 1, 27–35. MR 934999, DOI 10.1007/BF01229958
- Dmitriy Zhuk, A proof of CSP dichotomy conjecture, 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017, IEEE Computer Soc., Los Alamitos, CA, 2017, pp. 331–342. MR 3734241, DOI 10.1109/FOCS.2017.38
Additional Information
- Manuel Bodirsky
- Affiliation: Institute of Algebra, Technische Universität Dresden, Dresden, Germany
- MR Author ID: 693478
- ORCID: 0000-0001-8228-3611
- Email: manuel.bodirsky@tu-dresden.de
- Antoine Mottet
- Affiliation: Department of Algebra, Charles University in Prague, Czech Republic
- MR Author ID: 1135698
- ORCID: 0000-0002-3517-1745
- Email: mottet@karlin.mff.cuni.cz
- Miroslav Olšák
- Affiliation: Department of Algebra, Charles University in Prague, Czech Republic
- ORCID: 0000-0002-9361-1921
- Email: mirek@olsak.net
- Jakub Opršal
- Affiliation: Department of Computer Science, Durham University, Durham, United Kingdom
- MR Author ID: 1104311
- ORCID: 0000-0003-1245-3456
- Email: jakub.oprsal@durham.ac.uk
- Michael Pinsker
- Affiliation: Institute of Discrete Mathematics and Geometry, Technische Universität Wien, Austria; and Department of Algebra, Charles University in Prague, Czech Republic
- MR Author ID: 742015
- ORCID: 0000-0002-4727-918X
- Email: marula@gmx.at
- Ross Willard
- Affiliation: Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario, Canada
- MR Author ID: 183075
- ORCID: 0000-0002-3297-0453
- Email: ross.willard@uwaterloo.ca
- Received by editor(s): February 5, 2020
- Received by editor(s) in revised form: April 7, 2020
- Published electronically: October 14, 2020
- Additional Notes: The first and fourth authors were supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No 681988, CSP-Infinity).
The second author received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No 771005, CoCoSym).
The third and fifth authors received funding from the Czech Science Foundation (grant No 13-01832S)
The fourth author also received funding from the UK EPSRC (grant No EP/R034516/1).
The fifth author received funding from the Austrian Science Fund (FWF) through project No P32337.
The sixth author was supported by the Natural Sciences and Engineering Research Council of Canada.
A conference version of this material appeared at the Thirty-Fourth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 2019 \cite{TopologyIsRelevant}. - © Copyright 2020 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 374 (2021), 327-350
- MSC (2010): Primary 08B05, 03C05, 08A70; Secondary 03C10, 03D15
- DOI: https://doi.org/10.1090/tran/8179
- MathSciNet review: 4188185