A constraint satisfaction problem is a finite set, A, equipped with a (possibly) infinite set of relations, Sigma. An instance of CSP(Sigma) is a finite set of variable-tuples, each such tuple associated to a relation from Sigma. The question is: does there exist an evaluation of the variables such that the image of each tuple is contained in the relation to which it is associated.
It was conjectured in 1999 by Feder and Vardi that CSP problems do not admit a dichotomy-- that is, if P neq NP, then there exist CSP problems which are neither in P nor NP-complete. Recently a group of researchers led by Peter Jeavons correlate to a CSP problem Sigma on a finite set A with a finite algebra A_{Sigma}. They suggest that CSP's do admit a dichotomy and frame their counter-conjecture in simple algebraic terminology described at the talk.
Associated to a finite algebra A is a computational complexity problem, namely the word-problem for A: given two terms p and q in the language of A, is it true that p \approx q over A? Much work has been done by computer scientists and mathematicians in the last ten years classifying the computational complexity of word problems for various algebras, including rings, lattices, groups and semigroups. The speaker will briefly describe recent work of his own.
There are strong connections between CSP's and word-problems: every
CSP is co-polynomially equivalent to a word problem for some finite
algebra A. Several conjectures of the author and others will be
presented.