A proof of the algebraic tractability conjecture for monotone monadic SNP

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

Abstract

The logic MMSNP is a restricted fragment of existential second-order logic which can 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. The new universalalgebraic 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 ω-categorical structures; moreover, by a recent result of Hubička and Nešetřil, these structures can be expanded to homogeneous structures with finite relational signature and the Ramsey property.

Details

OriginalspracheEnglisch
FachzeitschriftSIAM journal on computing : a publication of the Society for Industrial and Applied Mathematics
Jahrgang50
Ausgabenummer4
PublikationsstatusVeröffentlicht - 2021
Peer-Review-StatusJa

Externe IDs

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

Schlagworte

Schlagwörter

  • Constraint satisfaction problems, Monotone monadic SNP, Polymorphisms