The Descriptive Complexity of Constraint Satisfaction

can be viewed as constraint-satisfaction problems.
This includes problems in database query optimization, machine vision,
belief maintenance, scheduling, temporal reasoning, type reconstruction,
graph theory, and satisfiability. All of these problems can be recast
as questions regarding the existence of homomorphisms between two
relational structures. It is well-known that the constraint
satisfaction problem is NP-complete. In practice, however, one often
encounters the situation where the target structure is fixed. This
gives rise to a class of constraint-satisfaction problems, denoted
CSP. This class is contained in NP. The first topic of this talk is
the question whether CSP has "intermediate" problems, i.e., problems
that are neither in P nor NP-complete. The second topic is an attempt to
understand the tractable fragment of CSP. We argue that there seems
to be only two reasons for tractability of problems in CSP. Finally,
we study the question whether nonuniform tractability results (i.e.,
for a fixed target structure) can uniformize (i.e., to a varying
target structure).