The Weak Base Method for Constraint Satisfaction
Gottfried Wilhelm · 2008
Constraint satisfaction problems are an important class of problems in complexity theory. They generalize many combinatorial problems as well as satisfiability problems and provide canonical complete problems for many complexity classes. The computational complexity of all Boolean constraint satisfaction problems was classified by Schaefer [Sch78] and reveals a dichotomic behavior that is conjectured to also hold for arbitrary domains [FV98]. Algebraic tools involving a Galois correspondence between clauses appearing in the constraint instances and sets of functions give a method to obtain complexity classifications in the constraint context. However, for many problems related to constraint satisfaction these tools cannot be applied. In this thesis we develop a method that allows to use a refined Galois correspondence to obtain complexity classifications for those problems. Afterwards we demonstrate our new method by classifying two constraint problems from different contexts: first we consider the balanced satisfiability problem, where we require the solutions to satisfy a global condition additionally to the local constraints given in the constraint instance. Then we turn to nonmonotonic logics and study the complexity of reasoning in default logic restricted to constraint formulas. In both cases we achieve full classifications using our new method as an essential tool. Finally we study the problem of enumerating all solutions of a given constraint instance. For the Boolean case a full classification has been achieved by Creignou and Hebrard [CH97]. We look at instances over arbitrary finite domains and present a template for new efficient enumeration algorithms. We achieve a first step towards a classification of the enumeration problem over the three-element domain.