Extended constraint satisfaction problems
Joanna Ochremiak · 2015
Motivation. Computer science is about effectively finding solutions that satisfy given specifications. To achieve this goal one develops algorithms that output a solution or determine its existence, analyses the complexity of those algorithms or proves that they do not exist, and looks for approximate solutions that provide the best possible trade-off between satisfying the specification and the effectiveness of an algorithm. The rich theory of computer science is developed to ultimately serve those purposes. Every specification can be seen as a list of constraints imposed on a desired solution. The theory of constraint satisfaction provides one way of formalising this intuition. Its study begun in the 70s independently in the fields of artificial intelligence, database theory, and graph theory. And since 1978, when the seminal paper of Schaefer [45] about the complexity of boolean constraint satisfaction problems (CSPs) was published, it has become of more and more importance. The CSP framework turned out to be very robust. Its different variants appear in many research areas of theoretical computer science. The power of constraint satisfaction lies in the fact that although it covers a large class of problems, its different variants still bear enough similarities to make transferring methods from one to another possible. Throughout the years, a very rich collection of mathematical tools got involved in the formal analysis of the CSP, from algebra, logic and model theory to probability, graph theory and combinatorics. Phrasing a problem in the constraint satisfaction framework gives one an additional insight into its structure and suggests tools that could be potentially used to solve it. This thesis provides more evidence in favour of the unifying approach of the constraint satisfaction paradigm. It concerns two different extensions of the classical constraint satisfaction problem. Firstly, we introduce a new variant of the CSP with a possibly infinite set of constraints in an instance. We show how it arises in the analysis of a rather natural model of computation, and allows us to understand its behaviour, as well as the expressive power of an associated logic. Secondly, we successfully use universal algebraic tools developed for the decision version