Monotone Monadic SNP 2: Proof of the Universal-algebraic Dichotomy Conjecture

Vortrag von Antoine Mottet

Veranstaltungsort: WIL C115
Beginn: 1. September 2017 um 13:45
Ende: 1. September 2017 um 14:15
iCal

The forbidden patterns problem of the set of vertex-coloured graphs {H1,…,Hk} is the decision problem of the form: given a finite graph G as input, is it possible to colour the vertices of G in a way that none of H1, …, Hk homomorphically maps to the resulting coloured graph. The logic MMSNP can be seen as a complexity class whose problems are forbidden patterns problems of finite sets of coloured relational structures. It was conjectured by Feder and Vardi that this complexity class exhibits a complexity dichotomy (i.e., that every forbidden patterns problem is in P or NP-complete). Feder and Vardi showed that every problem in MMSNP reduces in probabilistic polynomial-time to the CSP of a structure with finite domain, and Kun later derandomized this reduction. Thus, MMSNP and finite-domain CSPs are computationally equivalent.

Following up on Manuel's talk, I will present a completely new reduction from MMSNP to finite-domain CSPs that uses recent techniques and results from universal algebra, model theory, and Ramsey theory. This proves a stronger form of the Feder-Vardi-Kun result, and shows in particular that the Bodirsky-Pinsker tractability conjecture holds for all CSPs in MMSNP.