Do we have any characterization of groups with a decidable automorphism problem ? When it is decidable, Is there any results about the complexity of the automorphism problem in group with polynomial growth ? In the case of nilpotent group the word problem is known to be polynomial ... do we have any clue for the automorphism problem ? Does there exists groups with polynomial growth and undecidable automorphim problem ?
Thnaks.
By Gromov's result, a group with polynomial growth is virtually nilpotent, and hence virtually polycyclic. Segal proved that virtually polycyclic groups have solvable automorphism group and isomorphism problems. But I am not aware of any efficient algorithms. It is a difficult problem even for finite $p$-groups.