A note on the hardness of tree isomorphism
B. Jenner, Pierre McKenzie, Jacobo Torán · 2002
We prove that the tree isomorphism problem, when trees are encoded as strings, is NC/sup 1/-hard under DLOGTIME-reductions. NC/sup 1/-completeness thus follows from Buss's recent NC/sup 1/ upper bound. By contrast, we prove that testing isomorphism of two trees encoded as pointer lists is L-complete.