Investigating potential dichotomies above Feder and Vardi’s logic MMSNP

Feder and Vardi’s logic MMSNP was introduced in 1998 as a counterpart for the class of Constraint Satisfaction Problems (CSP). Namely, the complexity class of (problems definable by a sentence of) MMSNP is equivalent to the class CSP (in a sense of having a dichotomy) despite strictly containing it.

In particular, MMSNP enjoys a dichotomy as a consequence of the CSP dichotomy established independently by Bulatov and Zhuk in 2017.

There are several natural ways one might wish to study classes above that of problems definable in MMSNP. For example, we could enrich CSP by modifying the combinatorial rules that define CSP – this is the case of the Matrix Partition problems–; alternatively, we could relax some of the syntactic restrictions imposed on MMSNP and get a richer logical language – this is the case of the logic MMSNP2–.

We will focus in particular in this talk on Matrix Partition problems (MP) introduced by Hell et. al, and conjectured to follow a dichotomy.

We will highlight the differences between MP and CSP and discuss the areas in which we have been studying this class.