Temps de calcul pseudo-polynomial

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique théorique, et notamment en théorie de la complexité, un algorithme est appelé pseudo-polynomial[1] si sa complexité en temps est un polynôme en la valeur numérique de l'entrée.

Exemple[modifier | modifier le code]

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 n-2 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 .

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

Compléments[modifier | modifier le code]

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[modifier | modifier le code]

  1. Garey et Johnson, p. 79.
  2. La publication en revue scientifique date de 2004 : Manindra Agrawal, Neeraj Kayal et Nitin Saxena, « PRIMES is in P », Annals of Mathematics. Second Series, vol. 160, no 2,‎ , p. 781-793 (DOI 10.4007/annals.2004.160.781, Math Reviews MR2123939, zbMATH 02157791, lire en ligne)

(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[modifier | modifier le code]

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