Abstract: |
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
directed graphs. It is well-known that the constraint-satisfaction
problem is NP-complete. This motivated an extensive research program
into identify tractable cases of constraint satisfaction.
This research proceeds along two major lines. The first line of
research focuses on non-uniform constraint satisfaction, where the
target graph is fixed. The goal is to identify those traget graphs
that give rise to a tractable constraint-satisfaction problem. The
second line of research focuses on identifying large classes of source
graphs for which constraint-satisfaction is tractable. We show in
this talk how tools from graph theory, universal algebra, logic and
complexity theory, shed light on the tractability of constraint
satisfaction.
|