The Descriptive Complexity of Constraint Satisfaction

Moshe Y. Vardi
Rice University

A large class of problems in AI and other areas of computer science 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).