Authors: Carl Droms, Jacques Lewin and Herman Servatius

Reference: in Topology and Combinatorial Group Theory, Lecture Notes in Math. #1440, Springer-Verlag, 48--51, 1990.

Abstract: We examine the relationship between the complexity of the word problem for a given presentation and the complexity of the problem of determining the length of a shortest word equivalent to a given word.

We prove that the length of the element represented by a word in a free solvable group can be determined in polynomial time, and give an algorthm for doing so.