The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

TLDR

The study employs Datalog and group theory to analyze the computational structure of monotone monadic SNP and CSP. The authors aim to identify a large NP subclass exhibiting a dichotomy, present conjectures for this dichotomy, and analyze CSP subclasses to unify known polynomial‑time algorithms and characterize NP‑hardness. They use syntactic prescriptions, leverage Ladner’s theorem to justify restrictions, explore the class’s structure, and partition CSP into subclasses to unify algorithms and extract hardness properties. They isolate a monotone monadic SNP without inequality class that may exhibit a dichotomy and show that all problems in this class reduce to CSP.

Abstract

This paper starts with the project of finding a large subclass of NP which exhibits a dichotomy. The approach is to find this subclass via syntactic prescriptions. While the paper does not achieve this goal, it does isolate a class (of problems specified by) "monotone monadic SNP without inequality" which may exhibit this dichotomy. We justify the placing of all these restrictions by showing, essentially using Ladner's theorem, that classes obtained by using only two of the above three restrictions do not show this dichotomy. We then explore the structure of this class. We show that all problems in this class reduce to the seemingly simpler class CSP. We divide CSP into subclasses and try to unify the collection of all known polytime algorithms for CSP problems and extract properties that make CSP problems NP-hard. This is where the second part of the title, "a study through Datalog and group theory," comes in. We present conjectures about this class which would end in showing the dichotomy.