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

Research output: Contribution to book/conference proceedings/anthology/reportConference contributionContributedpeer-review

Contributors

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 that does not rely on the results of Kun. This new proof allows us to obtain a stronger statement and to verify the 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 -categorical structures; moreover, by a recent result of Hubika and Neetil, 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.

Details

Original languageEnglish
Title of host publicationProceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018
PublisherIEEE, New York [u. a.]
Pages105-114
Number of pages10
ISBN (electronic)9781450355834, 9781450355834
Publication statusPublished - 9 Jul 2018
Peer-reviewedYes

Conference

Title33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018
Duration9 - 12 July 2018
CityOxford
CountryUnited Kingdom

External IDs

ORCID /0000-0001-8228-3611/work/142241082

Keywords

ASJC Scopus subject areas