Given two Prufer sequences $P_1$ and $P_2$ that correspond to trees $T_1$ and $T_2$ of order $n$ what is the most efficient method to determine whether $T_1$ is isomorphic to $T_2$ as an unlabelled tree?
Having read about the difficulty of detecting isomorphic graphs via graph invariants (https://mathoverflow.net/questions/11631/complete-graph-invariants) I suspect this is a hard problem.