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$.

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$, and $P$ and $Q$ are of equal multiplicative order, find $P$.

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