Constraint satisfaction problems and expressiveness

Victor Dalmau

Universitat Pompeu Fabra

Constraint satisfaction problems arise in a wide variety of domains, such as combinatorics, logic, and artificial intelligence. In recent years, much effort has been directed towards classifying the complexity of all families of constraint satisfaction problems. It has been shown that it is possible to associate to every subclass of the CSP an algebra ${\bf A}$ such that the complexity the corresponding CSP is completely determined by the properties of ${\bf A}$.

Let ${\bf A}$ be any algebra over a finite universe. We define the expressiveness of ${\bf A}$ as the mapping $\hbox{ex}_{\bf A}:{\cal N}\rightarrow{\cal N}$ that given a natural number $n$ returns the number subuniverses of ${\bf A}^n$. Some algebras ${\bf A}$ that lead to tractable cases of the CSP such as Mal'tsev algebras, or algebras containing a near-unanimity operations among their term operations, satisfy the following property: $\log \hbox{ex}_{\bf A}(n)\leq p(n)$, for some polynomial $p$. We call any such algebra polynomially expressible. We conjecture that all polynomially expressible algebras give rise to families of constraint satisfaction problems solvable in polynomial time. In this talk we shall present some initial results in this direction.