Complexity of algebra and algebra of complexity
by
Mikhail Volkov
Ural State University (Ekaterinburg, Russia)

We present some recent ideas relating General Algebra and Computational Complexity. One connection here arises when one tries to understand complexity of algebra or, more precisely, complexity of some very basic algebraic algorithms. For instance, it turns out that answering fundamental questions such as "Does a finite algebra satisfies a given (quasi)identity?" or "Does a finitely generated (quasi)variety contain a given finite algebra?" may be computationally hard even for semigroups.

Yet another connection can be referred to as algebra of complexity. Here one isolates certain classes of important combinatorial problems (so called constraint satisfaction problems) and assigns each such class a finite algebra so that computational complexity of the class is completely determined by abstract properties of the algebra. Thus, we have a two-way road which leads to a number of surprising results and to several new intriguing research directions.

Date received: May 18, 2004