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