A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP

DOI10.1145/3209108.3209156zbMath1452.03084arXiv1802.03255OpenAlexW2964345483MaRDI QIDQ5145282

Antoine Mottet, Manuel Bodirsky, Florent R. Madelaine

Publication date: 20 January 2021

Published in: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1802.03255

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Model theory of finite structures (03C13) Equational classes, universal algebra in model theory (03C05) Higher-order logic (03B16)

Related Items (9)

In praise of homomorphisms ⋮ When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems ⋮ 𝜔-categorical structures avoiding height 1 identities ⋮ Pseudo‐loop conditions ⋮ An algebraic view on p-admissible concrete domains for lightweight description logics ⋮ Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems) ⋮ PROJECTIVE CLONE HOMOMORPHISMS ⋮ Using model theory to find decidable and tractable description logics with concrete domains ⋮ ASNP: a tame fragment of existential second-order logic

This page was built for publication: A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP