Conjugate permutations
Python 2, 87 bytes



f=lambda P,k:k&lt;1or len({sum([x==eval('L['*k+'x'+']'*k)for x in L])for L in P})&amp;f(P,k-1)


Try it online!

Takes input with P as a pair of both permutations and k their length. Outputs 1 for conjugates and 0 not.

This uses the result:


  Two permutations x and y are conjugate exactly if their k-th powers xk and yk have an equal number of fixed points for every k from 0 to n.


Two conjugate permutations satisfy this because their k-th powers are also conjugate, and conjugacy preserves the count of fixed points. 

It's less obvious that any two non-conjugate permutations always differ. In particular, conjugacy is determined by the sorted list of cycle lengths, and these can be recovered from the counts of fixed points. One way to show this is with linear algebra, though it might be overkill. 

Let X be the permutation matrix for x. Then, the number of fixed points of xk is Tr(Xk). These traces are the power sum symmetric polynomials of the eigenvalues of Xk with multiplicity. These polynomials for k from 0 to n let us recover the corresponding elementary symmetric polynomials of these eigenvalues, and therefore the characteristic polynomial and so the eigenvalues themselves. 

Since these eigenvalues are roots of unity corresponding to the cycles of x, from these we can recover the cycle sizes and their multiplicities. So, our "signature" identifies the permutation up to conjugation.