What is computational complexity of the following problem:
given two complex $n\times n$ matrices $A$ and $B$ check if there is a permutation matrix $P$ such that: $$B = P A P^T.$$
If it helps, one can assume that $A$ and $B$ are hermitian (or even that $A$ and $B$ are real and symmetric).
The problem stems from checking if two sets of vectors are related by an unitary rotation, see Sets of vectors related by a rotation - MathOverflow. In that context $A$ and $B$ are their Gramian matrices.
The problem is at least as hard as the graph isomorphism problem - take $A$ and $B$ as adjacency matrices.