Atlas home || Conferences | Abstracts | about Atlas

International Conference on Modern Algebra in conjunction with the 17th annual Shanks Lectures
May 21-24, 2002
Vanderbilt University
Nashville, TN, USA

Organizers
Jonathan Farley, Ralph Freese, Matthew Gould, Peter Jipsen, George McNulty, Miklos Maroti, Alexander Ol'shanskii, Steven Tschantz, Constantine Tsinakis, Matthew Valeriote

View Abstracts
Conference Homepage

Semigroup varieties and quasivarieties from complexity-theoretical viewpoint
by
Mikhail Volkov
Ural State University (Ekaterinburg, Russia)

Several `obvious' questions in algebra become very hard if one looks at them from the standpoint of feasible computations. Here is an example of such a question: given a finite semigroup S and a (quasi)identity, does S satisfy the (quasi)identity? Kharlampovich and Sapir (in their well known survey `Algorithmic problems in varieties', Int. J. Algebra Computation 5 (1995) 379-602) asked what is the complexity of this problem if one fixes S and considers the (quasi)identity as the input. Clearly, the problem belongs to the complexity class co-NP. I shall exhibit a 10-element semigroup for which the problem of checking quasiidentities is co-NP-complete and a 19-element semigroup for which the problem of checking identities is co-NP-complete. Several results and problems of similar flavor will be presented in order to show how a complexity-theoretical analysis of certain familiar algebraic situations reveals unexpected and fascinating problems.

Date received: December 29, 2001

Copyright © 2001 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caig-13.