Document Open Access Logo

Hrushovski’s Encoding and ω-Categorical CSP Monsters

Authors Pierre Gillibert , Julius Jonušas , Michael Kompatscher , Antoine Mottet , Michael Pinsker

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.131.pdf
  • Filesize: 0.61 MB
  • 17 pages

Document Identifiers

Author Details

Pierre Gillibert
  • Institut für Diskrete Mathematik und Geometrie, Technische Universität Wien, Austria
Julius Jonušas
  • Institut für Diskrete Mathematik und Geometrie, Technische Universität Wien, Austria
Michael Kompatscher
  • Department of Algebra, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
Antoine Mottet
  • Department of Algebra, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
Michael Pinsker
  • Institut für Diskrete Mathematik und Geometrie, Technische Universität Wien, Austria
  • Department of Algebra, Faculty of Mathematics and Physics, Charles University, Czech Republic

Funding

  • Gillibert, Pierre: received funding from the Austrian Science Fund (FWF) through projects No P27600 and P32337.
  • Jonušas, Julius: received funding from the Austrian Science Fund (FWF) through Lise Meitner grant No M 2555.
  • Kompatscher, Michael: supported by the grants PRIMUS/SCI/12 and UNCE/SCI/022 of Charles University Research Centre programs, as well as grant No 18-20123S of the Czech Science Foundation.
  • Mottet, Antoine: received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No 771005, CoCoSym).
  • Pinsker, Michael: received funding from the Austrian Science Fund (FWF) through projects No P27600 and P32337 and from the Czech Science Foundation (grant No 18-20123S).

Cite AsGet BibTex

Pierre Gillibert, Julius Jonušas, Michael Kompatscher, Antoine Mottet, and Michael Pinsker. Hrushovski’s Encoding and ω-Categorical CSP Monsters. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 131:1-131:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.131

Abstract

We produce a class of ω-categorical structures with finite signature by applying a model-theoretic construction - a refinement of an encoding due to Hrushosvki - to ω-categorical structures in a possibly infinite signature. We show that the encoded structures retain desirable algebraic properties of the original structures, but that the constraint satisfaction problems (CSPs) associated with these structures can be badly behaved in terms of computational complexity. This method allows us to systematically generate ω-categorical templates whose CSPs are complete for a variety of complexity classes of arbitrarily high complexity, and ω-categorical templates that show that membership in any given complexity class cannot be expressed by a set of identities on the polymorphisms. It moreover enables us to prove that recent results about the relevance of topology on polymorphism clones of ω-categorical structures also apply for CSP templates, i.e., structures in a finite language. Finally, we obtain a concrete algebraic criterion which could constitute a description of the delineation between tractability and NP-hardness in the dichotomy conjecture for first-order reducts of finitely bounded homogeneous structures.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatoric problems
Keywords
  • Constraint satisfaction problem
  • complexity
  • polymorphism
  • pointwise convergence topology
  • height 1 identity
  • ω-categoricity
  • orbit growth

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Libor Barto. Finitely related algebras in congruence distributive varieties have near unanimity terms. Canadian Journal of Mathematics, 65(1):3-21, 2013. Google Scholar
  2. Libor Barto. Finitely related algebras in congruence modular varieties have few subpowers. Journal of the European Mathematical Society, 20(6):1439-1471, 2018. Google Scholar
  3. 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. In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-12, 2017. Google Scholar
  4. Libor Barto, Michael Kompatscher, Miroslav Olšák, Trung Van Pham, and Michael Pinsker. Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures. Journal of Mathematical Logic, 19(2):#1950010, 2019. Google Scholar
  5. Libor Barto, Jakub Opršal, and Michael Pinsker. The wonderland of reflections. Israel Journal of Mathematics, 223(1):363-398, 2018. Google Scholar
  6. Libor Barto and Michael Pinsker. The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems. In Proceedings of the 31th Annual IEEE Symposium on Logic in Computer Science - LICS'16, pages 615-622, 2016. Google Scholar
  7. Libor Barto and Michael Pinsker. Topology is irrelevant. SIAM Journal on Computing, 49(2):365-393, 2020. Google Scholar
  8. Richard Beigel, Richard Chang, and Mitsunori Ogiwara. A relationship between difference hierarchies and relativized polynomial hierarchies. Mathematical Systems Theory, 26(3):293-310, 1993. Google Scholar
  9. Manuel Bodirsky and Martin Grohe. Non-dichotomies in constraint satisfaction complexity. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, pages 184-196. Springer Verlag, 2008. Google Scholar
  10. Manuel Bodirsky and Jan Kára. The complexity of temporal constraint satisfaction problems. Journal of the ACM, 57(2):1-41, 2009. A conference version appeared in the Proceedings of the Symposium on Theory of Computing (STOC) 2008. Google Scholar
  11. Manuel Bodirsky, Florent Madelaine, and Antoine Mottet. A universal-algebraic proof of the complexity dichotomy for monotone monadic snp. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '18, pages 105-114, 2018. Google Scholar
  12. Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz. Constraint satisfaction problems for reducts of homogeneous graphs. SIAM Journal on Computing, 48(4):1224-1264, 2019. A conference version appeared in the Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, pages 119:1-119:14. Google Scholar
  13. 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. Google Scholar
  14. Manuel Bodirsky, Antoine Mottet, Miroslav Olšák, Jakub Opršal, Michael Pinsker, and Ross Willard. ω-categorical structures avoiding height 1 identities. Transactions of the American Mathematical Society, 2020. Accepted for publication. Google Scholar
  15. Manuel Bodirsky and Michael Pinsker. Schaefer’s theorem for graphs. Journal of the ACM, 62(3):52 pages (article number 19), 2015. A conference version appeared in the Proceedings of STOC 2011, pages 655-664. Google Scholar
  16. Manuel Bodirsky and Michael Pinsker. Topological Birkhoff. Transactions of the American Mathematical Society, 367:2527-2549, 2015. Google Scholar
  17. Manuel Bodirsky, Michael Pinsker, and András Pongrácz. Projective clone homomorphisms. Journal of Symbolic Logic, 2019. To appear. Preprint https://arxiv.org/abs/1409.4601. URL: https://doi.org/10.1017/jsl.2019.23.
  18. Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 319-330, 2017. Google Scholar
  19. Tomás Feder and Moshe Y. Vardi. Monotone monadic SNP and constraint satisfaction. In Proceedings of the Symposium on Theory of Computing (STOC), pages 612-622, 1993. Google Scholar
  20. 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 Journal on Computing, 28:57-104, 1999. Google Scholar
  21. Mai Gehrke and Michael Pinsker. Uniform Birkhoff. Journal of Pure and Applied Algebra, 222(5):1242-1250, 2018. Google Scholar
  22. Pierre Gillibert, Yannis Jonušas, Michael Kompatscher, Antoine Mottet, and Michael Pinsker. When symmetries are not enough: a hierarchy of hard constraint satisfaction problems. Preprint, 2020. URL: http://arxiv.org/abs/2002.07054.
  23. Wilfrid Hodges. Model theory. Cambridge University Press, 1993. Google Scholar
  24. Michael Kompatscher and Trung Van Pham. A complexity dichotomy for poset constraint satisfaction. Journal of Applied Logics, 5(8):1663-1695, 2018. Google Scholar
  25. Richard E. Ladner. On the structure of polynomial time reducibility. Journal of the ACM, 22(1):155-171, 1975. Google Scholar
  26. Miklós Maróti and Ralph McKenzie. Existence theorems for weakly symmetric operations. Algebra Universalis, 59(3-4):463-489, 2008. Google Scholar
  27. Sylvain Schmitz. Complexity hierarchies beyond elementary. ACM Transactions on Computation Theory (TOCT), 8(1):3:1-3:36, 2016. URL: https://doi.org/10.1145/2858784.
  28. Dmitriy N. Zhuk. A proof of CSP dichotomy conjecture. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 331-342, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact