Algebraic Combinatorics Seminar
####
**
UNIVERSITY OF KENTUCKY **

ALGEBRAIC COMBINATORICS SEMINAR

845 PATTERSON OFFICE TOWER

SPRING 2004

####

##
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

####
Abstract:

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.