Algebraic Combinatorics Seminar


Dichotomy or not to be- that is the question!
Computational complexity and finite algebras

Professor Steve Seif
University of Louisville

Monday, February 2, 2004
1:00 pm, 845 Patterson Office Tower


Fundamental computational complexity problems are polynomially equivalent to CSP's-- for example, SAT, GRAPH N-COLORABILITY, the retraction problem for bipartite graphs, homomorphism extension problems for finite posets, in addition to other graph-homomorphism problems. CSP's occupy an important place in theoretical computer and AI.

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.