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

Computational Complexity of Problems in Universal Algebra
by
Clifford Bergman
Iowa State University
Coauthors: Giora Slutzki (ISU)

Algebraists have long considered algorithmic questions to be of central interest. Traditionally, the focus has been on the decidability of the problem under consideration. As early as 1953, Tarski proved that the equational theory of relation algebras is undecidable. More recently, in 1996, McKenzie did the same for the question of whether a given finite algebra is finitely based. With the development of the theory of computational complexity, it is possible to sharpen our discussion of algorithmic questions. In this talk I will survey what is known about these questions, and propose several open problems, some of which seem to be quite difficult.

Date received: December 31, 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-34.