Temps de calcul pseudo-polynomial

En informatique théorique, et notamment en théorie de la complexité, un algorithme est appelé pseudo-polynomial si sa complexité en temps est un polynôme en la valeur numérique de l'entrée (mais pas nécessairement en la taille en mémoire de l'entrée). Considérons le problème du test de primalité. On peut vérifier qu'un entier naturel donné n est premier en testant qu'il n'est divisible par aucun des entiers . Cela exige divisions, de sorte que le temps pris par cet algorithme naïf est linéaire en la valeur n . Néanmoins, cet algorithme n'est pas efficace, comme on pourrait le penser d'un algorithme dit linéaire, puisqu’il demande déjà des milliards d'opérations sur une donnée de neuf chiffres décimaux. De fait, en théorie de la complexité, la complexité d'un algorithme est calculée en fonction de la longueur de l'entrée (et non pas de sa valeur), et cette longueur est généralement logarithmique en la valeur. Ainsi, l’algorithme naïf de test de primalité est pseudo-polynomial, tout en étant en temps exponentiel. La différence apparaît plus clairement encore quand on compare un tel algorithme avec un algorithme véritablement polynomial comme l'algorithme naïf d'addition d'entiers : l'addition de deux nombres à neuf chiffres décimaux nécessite environ neuf étapes, cet algorithme est réellement polynomial en la longueur de l'entrée. Il y a bien un cas — théorique — où les concepts de temps polynomial et pseudo-polynomial coïncident, c'est le cas où les entrées sont données en écriture unaire. La longueur d'une donnée est égale à sa valeur, puisque c'est le nombre de « bâtons » nécessaires pour la représenter. Dans le cas du test de primalité, il existe un algorithme appelé l'algorithme AKS d'après les initiales des noms de leurs inventeurs, découvert en 2002, qui est réellement polynomial en la taille de la donnée : son temps de calcul, pour un nombre n, est de l'ordre de .