Derivation- bounded groups

Abstract

For some problems which are defined by combinatorial properties good complexity bounds cannot be found because the combinatorial point of view restricts the set of solution algorithms. In this paper we present a phenomenon of this type with the classical word problem for finitely presented groups. A presentation of a group is called En-derivation-bounded (En-d.b.), if a function kϵEn exists which bounds the derivations of the words defining the unit element. For En-d.b. presentations a pure combinatorial En-algorithm for solving the word problem exists. It is proved that the property of being En-d.b. is an invariant of finite presentations, but that the degree of complexity of the pure combinatorial algorithm may be as far as posible from the degree of complexity of the word problem itself.