Derivation- bounded groups

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 E_n-derivation-bounded (E_n-d.b.), if a function kϵE_n exists which bounds the derivations of the words defining the unit element. For E_n-d.b. presentations a pure combinatorial E_n-algorithm for solving the word problem exists. It is proved that the property of being E_n-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.