Victor Dalmau
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 such that the complexity the corresponding CSP is
completely determined by the properties of
.
Let be any algebra over a finite universe. We define the
expressiveness of
as the mapping
that given a natural number
returns the number
subuniverses of
. Some algebras
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:
, for some polynomial
. 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.