El problema de comprovar si un polinomi donat és un polinomi de permutació sobre un cos polinòmic es pot resoldre en temps final.
El problema de comprovar si un polinomi donat sobre un cos finit és un polinomi de permutació es pot resoldre en temps polinòmic .