Thursday, January 24, 2013 3:30 pm
-
3:30 pm
EST (GMT -05:00)
Ross Willard, Department of Pure Mathematics, University of Waterloo
"Graphs, posets, polymorphisms, and the Constraint Satisfaction Problem Dichotomy Conjecture, Part II"
This
is
a
continuation
of
last
week's
seminar.
I
will
have
identify
each
of
the
main
Maltsev
conditions
relevant
to
CSP
and
some
secondary
ones,
characterize
each
main
Maltsev
condition
by
a
class
of
structures
which
it
forbids
to
be
pp-interpretable,
and
state
the
conjectures
connecting
each
main
Maltsev
condition
to
a
computational
complexity
class.