  We study the average case complexity of the uniform membership problem for
subgroups of free groups, and we show that it is orders of magnitude smaller
than the worst case complexity of the best known algorithms. This applies to
subgroups given by a fixed number of generators as well as to subgroups given
by an exponential number of generators. The main idea behind this result is to
exploit a generic property of tuples of words, called the central tree
property. An application is given to the average case complexity of the
relative primitivity problem, using Shpilrain's recent algorithm to decide
primitivity, whose average case complexity is a constant depending only on the
rank of the ambient free group.

Group Theory;Computational Complexity