Whitehead's algorithm

Whitehead's algorithm is a method in combinatorial group theory for deciding whether two elements, or two sets of elements, of a finite rank free group are equivalent under an automorphism of that group. Developed by the mathematician J. H. C. Whitehead in a 1936 paper, the algorithm works by applying a sequence of elementary automorphisms, known as Whitehead automorphisms, to reduce the length of a word step by step until no shorter equivalent form can be found, then comparing the resulting minimal forms. Two words are automorphically equivalent exactly when this reduction process brings them to matching minimal representatives. The algorithm underlies the solution to the automorphism problem for free groups and has been extended to related decision problems in geometric group theory. Its worst case running time is understood for free groups of rank two, where it runs in polynomial time, but whether it remains polynomial for groups of higher rank is still an open question in the field.