FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP

Authors: Manuel Bodirsky, Florent Madelaine and Antoine Mottet

Paper Information

Title:A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
Authors:Manuel Bodirsky, Florent Madelaine and Antoine Mottet
Proceedings:LICS PDF files
Editors: Anuj Dawar and Erich Grädel
Keywords:MMSNP, constraint satisfaction problems, universal algebra, model theory, Ramsey theory, finite model theory, complexity dichotomy, polynomial-time tractability
Abstract:

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. Our approach uses the fact that every MMSNP sentence describes a finite union of CSPs for countably infinite ω-categorical structures; moreover, by a recent result of Hubicka and Nesetril, 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. In particular, we verify the more general Bodirsky-Pinsker dichotomy conjecture for CSPs in MMSNP.

Pages:10
Talk:Jul 11 11:20 (Session 64D)
Paper: