On the complexity of the endomorphism problem for free groups
Charles C. Sims · 2001
We say the endomorphism problem is solvable for an element W in a free group F if it can be decided effectively whether, given U in F, there is an endomorphism p of F sending W to U. In free groups the endomorphism problem is always solvable as it is equivalent to solving a certain type of equation, and an algorithm for finding solutions to arbitrary equations was provided by Makanin in 1980. However, Makanin's use of very difficult group theoretical techniques makes this algorithm impractical. This thesis analyzes an approach due to C. Edmunds that has been improved and implemented by C. Sims. It has been shown that this approach solves the endomorphism problem when W belongs to some restricted classes of words, such as quadratic words. However, it has been unclear whether this approach solves the problem for any other type of words. Here we prove that the approach provides an efficient algorithm for solving the endomorphism problem when W is a two-generator word. We show that when W is a two-generator word this algorithm solves the problem in time polynomial in the length of U.