Robin Hirsch posed in 1996 the Really Big Complexity Problem: classify the computational complexity of the network satisfaction problem for all finite relation algebras A. We provide a complete classification for the case that A is symmetric and has a flexible atom; in this case, the problem is NP-complete or in P. The classification task can be reduced to the case where A is integral. If a finite integral relation algebra has a flexible atom, then it has a normal representation B. We can then study the computational complexity of the network satisfaction problem of A using the universal-algebraic approach, via an analysis of the polymorphisms of B. We also use a Ramsey-type result of Nešetřil and Rödl and a complexity dichotomy result of Bulatov for conservative finite-domain constraint satisfaction problems.

A constraint satisfaction problem (CSP) is a computational problem where the input consists of a finite set of variables and a finite set of constraints, and where the task is to decide whether there exists a satisfying assignment of values to the variables. Depending on the type of constraints that we allow in the input, a CSP might be tractable, or computationally hard. In recent years, general criteria have been discovered that imply that a CSP is polynomial-time tractable, or that it is NP-hard. Finite-domain CSPs have become a major common research focus of graph theory, artificial intelligence, and finite model theory. It turned out that the key questions for complexity classification of CSPs are closely linked to central questions in universal algebra. This thesis studies CSPs where the variables can take values from an infinite domain. This generalization enhances dramatically the range of computational problems that can be modeled as a CSP. Many problems from areas that have so far seen no interaction with constraint satisfaction theory can be formulated using infinite domains, e.g. problems from temporal and spatial reasoning, phylogenetic reconstruction, and operations research. It turns out that the universal-algebraic approach can also be applied to study large classes of infinite-domain CSPs, yielding elegant complexity classification results. A new tool in this thesis that becomes relevant particularly for infinite domains is Ramsey theory. We demonstrate the feasibility of our approach with two complete complexity classification results: one on CSPs in temporal reasoning, the other on a generalization of Schaefer's theorem for propositional logic to logic over graphs. We also study the limits of complexity classification, and present classes of computational problems provably do not exhibit a complexity dichotomy into hard and easy problems.

The universal-algebraic approach has proved a powerful tool in the study of the complexity of CSPs. This approach has previously been applied to the study of CSPs with finite or (infinite) omega-categorical templates, and relies on two facts. The first is that in finite or omega-categorical structures A, a relation is primitive positive definable if and only if it is preserved by the polymorphisms of A. The second is that every finite or omega-categorical structure is homomorphically equivalent to a core structure. In this paper, we present generalizations of these facts to infinite structures that are not necessarily omega-categorical. (This abstract has been severely curtailed by the space constraints of arXiv -- please read the full abstract in the article.) Finally, we present applications of our general results to the description and analysis of the complexity of CSPs. In particular, we give general hardness criteria based on the absence of polymorphisms that depend on more than one argument, and we present a polymorphism-based description of those CSPs that are first-order definable (and therefore can be solved in polynomial time).

Many fundamental problems in artificial intelligence, knowledge representation, and verification involve reasoning about sets and relations between sets and can be modeled as set constraint satisfaction problems (set CSPs). Such problems are frequently intractable, but there are several important set CSPs that are known to be polynomial-time tractable. We introduce a large class of set CSPs that can be solved in quadratic time. Our class, which we call EI, contains all previously known tractable set CSPs, but also some new ones that are of crucial importance for example in description logics. The class of EI set constraints has an elegant universal-algebraic characterization, which we use to show that every set constraint language that properly contains all EI set constraints already has a finite sublanguage with an NP-hard constraint satisfaction problem.

This paper studies peek arc consistency, a reasoning technique that extends the well-known arc consistency technique for constraint satisfaction. In contrast to other more costly extensions of arc consistency that have been studied in the literature, peek arc consistency requires only linear space and quadratic time and can be parallelized in a straightforward way such that it runs in linear time with a linear number of processors. We demonstrate that for various constraint languages, peek arc consistency gives a polynomial-time decision procedure for the constraint satisfaction problem. We also present an algebraic characterization of those constraint languages that can be solved by peek arc consistency, and study the robustness of the algorithm.

Such problems are that each relation R can be defined by a Boolean combination frequently intractable, but there are several important of equations over the signature,, andc, which are set CSPs that are known to be polynomial-time function symbols for intersection, union, and complementation, tractable. We introduce a large class of set CSPs respectively. Details of the formal definition and many that can be solved in quadratic time. Our class, examples of set constraint languages can be found in Section which we call EI, contains all previously known 3. The choice of N is just for notational convenience; tractable set CSPs, but also some new ones that as we will see, we could have selected any infinite set for are of crucial importance for example in description our purposes. In the following, a set constraint satisfaction logics. The class of EI set constraints has an problem (set CSP) is a problem of the form CSP(Γ) for a elegant universal-algebraic characterization, which set constraint language Γ. It has been shown by Marriott and we use to show that every set constraint language Odersky [Marriott and Odersky, 1996] that all set CSPs are that properly contains all EI set constraints already contained in NP; they also showed that the largest set constraint has a finite sublanguage with an NPhard constraint language, which consists of all relations that can be satisfaction problem.

We introduce a new tractable temporal constraint language, which strictly contains the Ord-Horn language of Buerkert and Nebel and the class of AND/OR precedence constraints. The algorithm we present for this language decides whether a given set of constraints is consistent in time that is quadratic in the input size. We also prove that (unlike Ord-Horn) this language cannot be solved by Datalog or by establishing local consistency.