Temps de calcul pseudo-polynomial

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 ${\displaystyle \{2,3,\dots ,\surd n\}}$. Cela exige ${\displaystyle \surd n-1}$ 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é 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[2], 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 ${\displaystyle O((\log {n})^{6})}$.

Un autre exemple d'un problème soluble en temps pseudo-polynomial, mais pour lequel aucun algorithme polynomial n'existe, sauf si P=NP, est le problème du sac à dos.

Un problème NP-complet pour lequel il existe un algorithme en temps pseudo-polynomial connue est appelé problème faiblement NP-complet (en). Un problème NP-complet est un problème fortement NP-complet (en) s'il est prouvé qu'il ne peut pas être résolu par un algorithme pseudo-polynomial à moins que P = NP. Les problèmes NP-difficiles faibles et forts sont définis de manière analogue.

• (en) Michael R. Garey et David S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, New York, W. H. Freeman and Company, 1979, 338 p. (ISBN 0-7167-1045-5).

• Portail de l'informatique théorique