71 KAM Mathematical Colloquium

Abstract

T. Feder and M. Vardi conjectured in 1990 that every instance of the constraint satisfaction problem is either tractable, i.e., is computable by a Turing machine working in polynomial time, or else is $NP$-complete. A classical result of universal algebra implies that for each finite relational structure $\m t$, the instance $\mbox{CSP}(\m t)$ of $CSP$ has a computational complexity determined just by the clone $\mbox{Poly}(\m t)$ consisting of all homomorphisms $f: \m t^n\rightarrow \m t$ (for arbitrary positive integers $n$). If $\mbox{Poly}(\m t)$ has no operations satisfying certain equations, then very many relations must be definable from the basic relations of $\m t$ via primitive positive definitions in first order logic. In this case, $\mbox{CSP}(\m t)$ is $NP$-complete.

These considerations led A. Bulatov, P. Jeavons and A. Krokhin to conjecture in 2000 that $\mbox{CSP}(\m t)$ is tractable (i.e., polynomial time computable) iff $\mbox{Poly}(\m t)$ contains a ``non-trivial operation''. By now, the appropriate meaning of ``non-trivial operation'' has stabilized as: an operation $s(x,y,z,u)$ satisfying the equations $s(x,x,x,x)=x$ and $s(x,y,z,z)=s(y,z,x,y)$ over $T$. The conjecture of Bulatov-Jeavons-Krokhin implies the Feder-Vardi dichotomy conjecture, and in light of some thirty-year-old developments in universal algebra, is plausible. The famous $P=NP$ conjecture is equivalent to Feder-Vardi combined with the statement that in some reasonable sense, every problem in $NP$ is computationally equivalent to a problem in $CSP$.

None of these conjectures have been proved, but they have produced a strong flow of beautiful results combining algebra, combinatorics, and logic. In my talk, I will strive to clearly illuminate these developments.
 

O přednášejícím

Profesor Ralph McKenzie studoval na univerzite v Coloradu a pak byl dlouholetym profesorem na Kalifornske univerzite v Berkeley (kde je dosud emeritnim profesorem). Od roku 1994 je profesorem na Vanderbiltove universite v Nashvillu. Byl rovnez hostem prednich svetovych instituci (Institute for Advanced Studies v Princetonu, ETH Zurich a Ulamuv profesor na Univerzite v Coloradu).

Hlavnim oborem Ralpha McKenzieho je algebra, logika a teorie mnozin. Bez nadsazky je mozne tvrdit, ze Ralph McKenzie je jednim z nejvlivnejsich algebraiku a zvlaste v univerzalni algebre je jeho postaveni naprosto jedinecne. Seznam jeho temer 60 spoluautoru se cte jako ``Kdo je kdo'' v univerzalni algebre a velke mnozstvi uspesnych zaku se stara o sireni jeho vehlasu. Jeho rozsahla publikacni cinnost zahrnuje vyreseni rady klasickych problemu (napr. problemy A. Tarskeho a G. Birkhoffa). Ralph je rovnez autorem rady knih, vcetne dnes jiz klasicke Algebras, Lattices and Varieties (spolu s G. McNultym a W. Taylorem) a monumentalnich ctyr svazku sebranych spisu Alfreda Tarskeho (spolu S. Givanem).

Vztahy Ralpha McKenzieho k ceske matematice jsou dlouhodobe a intenzivni a zahrnuji radu praci hlavne s Jaroslavem Jezkem a dalsimi (vcetne vyreseni stareho problemu V. Mullera, J. Pelanta a J. N. o turnajovych algebrach).

Vedecka prace prof. McKenzieho je vsestranna a definujici obor univerzalni algebry v ramci soucasne matematiky a informatiky. O tom ostatne svedci i jeho prazske kolokvium, ktere je venovano souvislostem univerzalni algebry a problemum optimalizacnim (tzv. Contstraint Satisfaction Problems).