Classifying the Complexity of Constraints Using Finite Algebras

By Andrei A. Bulatov, Peter G. Jeavons, Andrei A. Krokhin. SIAM journal on computing (Print), 2005

604 citations recorded by the source corpus.

Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. Here we show that any set of relations used to specify the allowed forms of constraints can be associated with a finite universal algebra and we explore how the computational complexity of the corresponding constraint satisfaction problem is connected to the properties of this algebra. Hence, we completely translate the problem of classifying the complexity of restricted constraint satisfaction problems into the language of universal algebra. We introduce a notion of "tractable algebra," and investigate how the tractability of an algebra relates to the tractability of the smaller algebras which may be derived from it, including its subalgebras and homomorphic images. This allows us to reduce significantly the types of algebras which need to be classified. Using our results we also show that if the decision problem associated with a given collection of constraint types can be solved efficiently, then so can the corresponding search problem. We then classify all finite strictly simple surjective algebras with respect to tractability, obtaining a dichotomy theorem which generalizes Schaefer's dichotomy for the generalized satisfiability problem. Finally, we suggest a possible general algebraic criterion for distinguishing the tractable and intractable cases of the constraint satisfaction problem.

Subfields: Computer Networks and Communications, Software, Signal Processing

View Paper: https://www.semanticscholar.org/paper/fb92ed698118d98ff5f1e739652a099fb5805134

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Software

Andrei A. Bulatov

In Signal Processing

Citations in the corpus

Varieties with few subalgebras of powers (2009, background): “a conjecture about the set SPfin(A) of subalgebras of finite Cartesian powers of a finite universal algebra A [20, 5].”
Combinatorial problems raised from 2-semilattices (2006, methodology): “For several classes of finite algebras, the tractable algebras have been characterized: 2- and 3-element algebras [2,4,42], strictly simple algebras [9], finite semigroups [8].”
Finitely Related Algebras in Congruence Distributive Varieties Have Near Unanimity Terms (2013, background): “Moreover, Bulatov, Jeavons and Krokhin proved [8] that the complexity depends only on the variety generated by A (i.”
A strong Mal’cev condition for locally finite varieties omitting the unary type (2010, neutral): “This connection was taken further in [5].”
A Linear Programming Approach to Max-Sum Problem: A Review (2007, background): “In the latter, a lot of research has been done and mathematicians seem to be close to complete classification [52].”
A Proof of CSP Dichotomy Conjecture (2017, background): “Later, the dichotomy conjecture was formulated in several different forms (see [7]).”