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é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[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})}$.

Problème du sac à dos : comment remplir un sac en maximisant la somme des valeurs des objets emportés, sans dépasser le poids limite ?

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. Le problème du sac à dos est le suivant :

• entrée : un poids limite W, et une collection d'objets, chaque objet possède une valeur et un poids ;
• sortie : une sélection des objets à mettre dans le sac afin de maximiser la somme des valeurs des objets emportés, sans dépasser le poids limite.

Dans ce problème, on donne des nombres en entrée : un poids limite et les valeurs et poids de chaque objet. Par exemple, le poids limite W peut être de 15kg. Un algorithme est dit polynomial lorsque le temps d'exécution est polynomial en la taille de l'entrée, notamment en la taille de W, i.e. le nombre de bits qu'il faut pour écrire W, qui est de l'ordre de grandeur de log W (par exemple 15, en binaire s'écrit 1111 et requiert donc 4 bits). Ici, pour un algorithme pseudo-polynomial, on autorise à ce que le temps soit polynomial en le nombre W. Il existe des algorithmes obtenus via programmation dynamique, notamment en temps O(n² V) où V est la valeur de l'objet le plus cher[3].