The Nielsen reduction and P-complete problems in free groups (Q760500)

This paper is written very much for the computer scientist. The authors consider various problems concerning free groups, such as: the generalized word problem; the determination of shortest coset representatives modulo a given subgroup; to decide whether two subgroups are equal or isomorphic; to decide whether a given set of elements freely generates a subgroup, to decide whether a subgroup has finite index. They show that these problems are polynomially time complete under log-space reducibility. The main tool used is a careful analysis of the Nielsen reduction process.