How hard is the word problem?

Sarah Rees, University of Newcastle, UK,

Keywords

word problem, decision problems, formal language classes, complexity

Status

published in refereed Proceedings of Conference for European Women in Mathematics, Varna, Bulgaria, September 2002.

Abstract

When the word problem of a group is soluble, it is natural to ask how hard the problem is. It is standard to use bounds on time, or on space, or at least to use measures which give information about those bounds. It is also common to analyse the type of computational machine which is needed to perform the calculation (which could range from the most general Turing machine to a simple finite state automaton). This survey article introduces and compares briefly some of these different measures of complexity.

The preprint is available as gzipped dvi (12 kB) and postscript (36 kB) files.

Alternatively, you can request a copy by e-mailing me.