Technical Perspective: Constraint Satisfaction Problems and Computational Complexity

Consider the following very general setting for computational problems. An instance is presented as a set of variables taking values in a finite domain, together with a set of constraints on those variables. Each constraint applies to a certain tuple of variables and imposes a certain relation on the values they may take. The imposed relations come from an agreed "constraint language." We ask the question: Does there exist an assignment to the variables that simultaneously satisfies all the constraints? So, if the domain has nine elements and the constraint language contains the binary relation "not equal to," then we could express the problem of whether the vertices of a given graph can be properly colored with just nine colors. Or, more picturesquely, we could specify an arbitrary instance of Sudoku. (Technically, we would also require nine unary relations picking out the nine values in the domain.)

It takes only a little imagination to come up with a wealth of problems in scheduling and planning that can be expressed as Constraint Satisfaction Problems (CSPs) within an appropriate constraint language. It should come as no surprise, then, that CSPs have an important place in the fields of artificial intelligence and operations research. But why should there be such an interest in CSPs within the computational complexity community? Well, each constraint language (set of allowed constraint relations) defines a particular class of CSPs, and, as the constraint language becomes richer, the computational complexity of the corresponding class of CSPs becomes potentially greater. Classifying the computational complexity of the infinite array of possible constraint languages provides a challenging and stimulating task for complexity theorists, and hopefully one that has some practical value too.

The starting point was a result of Schaefer, which completely classified the computational complexity of CSPs in the case of a two-element (Boolean) domain. He identified certain polynomial-time solvable cases, for example, where all constraints can be expressed as conjunctions of Horn clauses. But the remarkable part of his result is that all other cases are NP-complete. In other words, he identified a dichotomy within Boolean CSPs—under the assumption P ≠ NP—between ones solvable in polynomial time, and ones that are NP-complete. This is significant, as a similar dichotomy is known not to exist in NP itself. There is no contradiction here, as not every problem in NP is expressible as a CSP. For example, it is not possible to express the Hamiltonian Cycle problem (a stripped-down version of the infamous Traveling Salesman problem) in any finite constraint language.

An article by Feder and Vardi provided a major spur to work on the computational complexity of CSPs. It would not be appropriate to describe their work in detail here, beyond noting they conjectured that a complexity dichotomy holds for the entire class of CSPs, not just ones over the Boolean domain. It transpires that the technical difficulties encountered when attempting to generalize Schaefer’s dichotomy to domains with more than two values are extreme, and the Feder-Vardi conjecture remains unresolved to this day. Fortunately, much progress has been made on related problems and special cases, making this a lively and dynamic area.

In the following paper, Bulatov and Marx deal with just such a related problem. Suppose the domain is Boolean, and the constraint language consists of the single binary relation "nand." This class of CSPs contains the n-Queens Problem since we can use this binary relation to express the rule that we are not allowed to have a queen at this position and that one. Well, not quite, since we must also insist there are n queens in all on the board, to deny the trivial solution with no queens! One way to incorporate such problems into the CSP framework is by adding a global cardinality constraint that determines the number of variables that take on each of the values in the underlying domain, in this instance that n of the variables should be set to "true." This extended class of "CCSPs" is the subject of the paper. Again, it is possible to imagine less frivolous examples of CCSPs than the 8-Queens Problem. For example, in determining locations for a number of facilities, one would want to ensure not only that various proximity and capacity constraints are met, but that the total number of facilities is within budget. Note that a cardinality constraint may increase computational complexity: the single relation "nand" in isolation leads to trivial CSPs (just set every variable to "false"), but adding a cardinality constraint yields the NP-complete problem "Maximum Independent Set."

Aside from establishing a dichotomy theorem for CCSPs, the authors provide an excellent introduction to the concerns and techniques of researchers in the computational complexity of CSPs. Intuition having been quickly developed in a sequence of examples and counterexamples, the reader is introduced to some of the tricks of the trade. A basic challenge in analyzing the computational complexity of CSPs is the following: Although the constraint language may be small, nevertheless these explicitly given relations can be combined (together with some extra variables) to generate a rich variety of derived, or "pp-definable" relations. One effective way to gain control over the ramifications of pp-definable relations is to transfer to a dual world of so-called polymorphisms: operations under which the class of definable relations is invariant. All this rich circle of ideas may be glimpsed in this study of CSPs with cardinality constraints.

Back to Top

Back to Top