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).

Exemples

Test de primalité

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

Sac à dos

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.

Compléments

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.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Pseudo-polynomial time » (voir la liste des auteurs).

Bibliographie

• (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).