  In 1951, Higman constructed a remarkable group $$H=\left\langle a,b,c,d \,
\left| \, b^a = b^2, c^b = c^2, d^c = d^2, a^d = a^2 \right. \right\rangle$$
and used it to produce the first examples of infinite simple groups. By
studying fixed points of certain finite state transducers, we show the
conjugacy problem in $H$ is decidable (for all inputs). Diekert, Laun and
Ushakov have recently shown the word problem in $H$ is solvable in polynomial
time, using the power circuit technology of Myasnikov, Ushakov and Won.
Building on this work, we show in a strongly generic setting that the conjugacy
problem has a $O(n^7)$ polynomial time solution.
