A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP

DOI10.1145/3209108.3209156zbMATH Open1452.03084arXiv1802.03255OpenAlexW2964345483MaRDI QIDQ5145282FDOQ5145282

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)

Abstract: The logic MMSNP is a restricted fragment of existential second-order logic which allows to express many interesting queries in graph theory and finite model theory. The logic was introduced by Feder and Vardi who showed that every MMSNP sentence is computationally equivalent to a finite-domain constraint satisfaction problem (CSP); the involved probabilistic reductions were derandomized by Kun using explicit constructions of expander structures. We present a new proof of the reduction to finite-domain CSPs which does not rely on the results of Kun. This new proof allows us to obtain a stronger statement and to verify the more general Bodirsky-Pinsker dichotomy conjecture for CSPs in MMSNP. Our approach uses the fact that every MMSNP sentence describes a finite union of CSPs for countably infinite $omega$-categorical structures; moreover, by a recent result of Hubiv{c}ka and Nev{s}etv{r}il, these structures can be expanded to homogeneous structures with finite relational signature and the Ramsey property. This allows us to use the universal-algebraic approach to study the computational complexity of MMSNP.

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

Recommendations

• On the complexity of MMSNP
• Partially ordered connectives and monadic monotone strict NP
• Constraint Satisfaction, Logic and Forbidden Patterns
• scientific article; zbMATH DE number 2191987
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

Mathematics Subject Classification ID

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

Cited In (13)

• In praise of homomorphisms
• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
• PROJECTIVE CLONE HOMOMORPHISMS
• 𝜔-categorical structures avoiding height 1 identities
• When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems
• Pseudo‐loop conditions
• Partially ordered connectives and monadic monotone strict NP
• An algebraic view on p-admissible concrete domains for lightweight description logics
• Using model theory to find decidable and tractable description logics with concrete domains
• Smooth approximations and CSPs over finitely bounded homogeneous structures
• Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145282)