2018/02/09 by Manuel Bodirsky, Bodirsky, Manuel, Florent Madelaine +3 · 2 citations
Computer Science · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.1802.03255
openalex publication_date 2018/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The logic MMSNP is a restricted fragment of existential second-order logic\nwhich allows to express many interesting queries in graph theory and finite\nmodel theory. The logic was introduced by Feder and Vardi who showed that every\nMMSNP sentence is computationally equivalent to a finite-domain constraint\nsatisfaction problem (CSP); the involved probabilistic reductions were\nderandomized by Kun using explicit constructions of expander structures. We\npresent a new proof of the reduction to finite-domain CSPs which does not rely\non the results of Kun. This new proof allows us to obtain a stronger statement\nand to verify the more general Bodirsky-Pinsker dichotomy conjecture for CSPs\nin MMSNP. Our approach uses the fact that every MMSNP sentence describes a\nfinite union of CSPs for countably infinite \ω-categorical structures;\nmoreover, by a recent result of Hubi vcka and Ne vset vril, these\nstructures can be expanded to homogeneous structures with finite relational\nsignature and the Ramsey property. This allows us to use the\nuniversal-algebraic approach to study the computational complexity of MMSNP.\n