Complexity Results for Boolean Constraint Satisfaction Problems (English shop)

Preview

Table of Contents, Datei (22 KB)
Extract, Datei (290 KB)

My dissertation deals with Boolean constraint satisfaction problems (CSP for short). A constraint consists of a set of variables and a (Boolean) relation that restricts the assignments of certain tuples of variables. A CSP is then the question of whether, for a given set of constraints, there exists an assignment of all variables that satisfies all constraints simultaneously. This CSP and some of its derivations are examined from the perspective of complexity theory. The algebraic method is used as an important instrument for determining the complexity of CSP. It makes use of the complete classification, found by Emil Post, of all classes of Boolean functions closed under superposition (clones). The closure of a set of functions under superposition means that the set of functions is closed under arbitrary compositions. The Post lattice, named after him, shows the complete inclusion structure of the clones. In combination with Galois theory, this has already made it possible to give many elegant proofs. Among other things, the dichotomy result of Thomas Schaefer was thereby proved anew. It states that the Boolean CSP, depending on the admitted Boolean constraints, is either in P or NP-complete.