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 exists a permutation matrix $P$ such that $P A P^T=B$.

Assume $A, B$ have $k$ distinct entries where $k$ is large. 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.

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.

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.

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 exists a permutation matrix $P$ such that $P A P^T=B$.

Assume $A, B$ have $k$ distinct entries where $k$ is large. 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.