Here all matrices are square $n \times n$ with integer entries.
If you prefer, all entries are $0-1$.

Observation: the discrete logarithm for permutation matrices is
polynomial in $n$, since the largest prime factor of the order
is small and we can apply small subgroup attack.

Let $P$ be permutation matrix.

What is the complexity of the following problem:
Given matrices $A,B,Q$, such that $B=P A P^T=P A P^{-1}$ and $Q=P^x$, find $P$.

$x$ is unknown.
In the graph isomorphism problem we are not given $Q$.