This is related to graph isomorphism.

Here matrices are square $n \times n$ with non-negative integer entries.

Two matrices $A,B$ are permutation similar if there exist permutation matrix $P$ such that $P A P^T=B$.

Assume $A,B$ have $k$ distinct entries where $k$ is large.

Q1 What is the complexity of finding $P$ as function of $n,k$?

In graph isomorphism the matrices are $0-1$ with $k=2$.

I expect large $k$ to help.