THE COMPUTATIONAL STRUCTURE OF MONOTONE MONADIC SNP AND CONSTRAINT SATISFACTION - A STUDY THROUGH DATALOG AND GROUP-THEORY

This paper starts with the project of finding a large subclass of NP w hich exhibits a dichotomy. The approach is to find this subclass via s yntactic prescriptions. While the paper does not achieve this goal, it does isolate a class (of problems specified by) ''monotone monadic SN P without inequality'' which may exhibit this dichotomy. We justify th e placing of all these restrictions by showing, essentially using Ladn er's theorem, that classes obtained by using only two of the above thr ee restrictions do not show this dichotomy. We then explore the struct ure of this class. We show that all problems in this class reduce to t he seemingly simpler class CSP. We divide CSP into subclasses and try to unify the collection of all known polytime algorithms for CSP probl ems and extract properties that make CSP problems NP-hard. This is whe re the second part of the title, ''a study through Datalog and group t heory,'' comes in. We present conjectures about this class which would end in showing the dichotomy.