Das Problem der Überprüfung, ob ein gegebenes Polynom ein Permutationspolynom über einem Polynomfeld ist, kann in letzter Zeit gelöst werden.
Das Problem des Testens, ob ein gegebenes Polynom über einem endlichen Feld ein Permutationspolynom ist, kann in Polynomialzeit gelöst werden.