A matter of great interest to theoretical computer scientists, logicians, and algebraists is the computational complexity of decision problems, i.e., how much resources (such as time or memory space) a computer program requires, as a function of the size of the input, to solve the problem.

Consider the following simple combinatorial problem, which is known as 2-Colorability: you are given a graph, i.e., a set of vertices some pairs of which are joined by an edge, and the goal is to determine whether it is possible to color the vertices with one of two colors, say red and blue, such that vertices joined by an edge get different colors. If the graph has n vertices, then there are 2ⁿ different possible colorings. At one microsecond per coloring, an exhaustive search for a proper coloring for a graph with 50 vertices could take up to ... 35 years! However, there is an ingenious shortcut: indeed, it is known that a graph is 2-colorable precisely when it contains no sequence of edges forming a cycle of odd length. The search for such cycles can be done rather efficiently. As a matter of fact, this search can be carried out in a number of steps that is bounded by a quadratic polynomial in n, which implies that even on a graph with 100 vertices the search will be over in a fraction of a second.

One may ask the same question for 3 colors. Although 2-Colorability and 3-Colorability may appear to be very similar problems, there is yet no known shortcut for the latter problem, and most experts believe that there is none, i.e., in essence, one cannot do much better than an exhaustive search. The fundamental problem of proving this widely held hunch, known as the P vs. NP question, has been at the core of research in theoretical computer science for the past 40 years, and has been identified by the Clay Institute as one of the 7 Millennium Prize Problems, alongside the Riemann Hypothesis and the Yang-Mills Conjecture.

The Constraint Satisfaction Problem (or CSP) is a general formulation of this type of decision question. Suppose that we are given a set of variables X₁, X₂, ..., X_n and a set of constraints C₁, C₂, ..., C_m. Here a constraint is an equation or a relation on the variables. Further suppose that we are provided with a domain of values that the variables can take. The fundamental question is whether these equations or constraints can be ``solved"; more precisely, we want to determine if values can be assigned to the X_j so that all the constraints are satisfied simultaneously. In the coloring problems above, one can view the vertices as the variables, the colors as the values to assign to the variables, and the edges as the constraints (every two vertices connected via an edge must be assigned different colors). An example with a more algebraic flavor has as instances systems of linear equations over a finite field, and the question is to determine whether the system admits a solution. Constraint satisfaction problems arise in a variety of guises in several different areas of mathematics and computer science, from the very general Boolean Satisfiability problem in logic to more concrete problems, such as scheduling problems, evaluation of database queries, design and layout problems, three-dimensional interpretations of two-dimensional drawings in computer vision, and even Sudoku puzzles.

The overall goal of this field, and of the discussions at this workshop, is to classify CSPs according to their complexity. Some problems, such as solving a system of linear equations, have an efficient algorithm (Gaussian elimination) that allows the problem to always be solved in time bounded by a polynomial in the size of the input. Other problems (such as the question of 3-coloring a graph) are NP-Complete; in particular, they are as hard as any other problem in the class of constraint satisfaction problems, and as mentioned earlier, believed to be intrinsically hard. The hope is that the machinery and techniques of universal algebra and logic can provide some general rules for pinpointing the exact complexity of CSPs and, in particular, telling whether a problem is easy or hard.

From any set of constraints, one can construct a universal algebra. Given an algebra A, we may consider the collection of all algebras that one obtains by taking powers or quotients or homomorphic images; this collection of algebras is called the variety generated by A. It is known that if two CSPs generate the same variety, then they are equally easy or hard. We would like to identify properties of the algebra that tell us whether the original problem (from which A arises) is easy or hard.

Garrett Birkhoff proved fifty years ago that a variety (as defined above) is determined by a system of equations. The type of equations that occur here can tell us whether the original problem is easy or hard. An interesting example occurs when, using the basic operations of the algebra A, we can build an operation M that is ternary (i.e., has three variables) and satisfies the identities M(x,x,y) = M(x,y,x)=M(y,x,x)=x, for all x, y ∈ A. We call such an M a majority operation. It is known that when such a majority operation exists, then the associated constraint satisfaction problem has an efficient algorithm. This is an ideal example of algebra informing the algorithmic complexity of constraint satisfaction problems.

Another approach that has been fruitful consists of describing the unsatisfiable instances of a CSP in a suitable logical formalism. If the logic used has good algorithmic properties, then the CSP at hand can be efficiently solved. In fact, a very large class of tractable CSPs (different in character from linear equations) can be solved this way. An important example of such a logic is Datalog (a variant of the programming language Prolog), which was originally designed as a language for expressing database queries, but turned out to be able to capture numerous CSPs, including 2-Colorability.

Remarkably, although apparently very distinct, the algebraic and the logic approach have been seen recently to be inextricably linked. Furthermore, the interaction between the two approaches has led to a deeper understanding of the algorithmic methods that are relevant to the study of the constraint satisfaction problem. The AIM workshop was a meeting ground for algebraists, logicians, and theoretical computer scientists with common interests and goals. The result was a vigorous exchange of ideas and development of new attacks on these important questions.