Complexity of higher order residues
Yes, there are good (efficient) algorithms.  This is completely solved, and the algorithms are widely used in the cryptographic community.

If $\gcd(n,p-1)=1$, then everything is a $n$th residue.

If $n$ divides $p-1$, then $a$ is a $n$th residue if and only if $a^{(p-1)/n} \equiv 1 \pmod p$.

If $1&lt;\gcd(n,p-1)&lt;n$, $a$ is a $n$th residue if and only if it is a $\gcd(n,p-1)$-th residue (see previous case).

For more details, see Finding roots in ℤp on Crypto.SE.