  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.
