Un algorithme peut sembler rapide sur le papier et devenir impraticable dès que les nombres manipulés grandissent. C’est précisément ce paradoxe que désigne la complexité pseudo-polynomiale, une notion essentielle pour comprendre certains algorithmes d’optimisation très utilisés en informatique, en logistique ou en recherche opérationnelle.
On parle de complexité pseudo-polynomiale lorsqu’un algorithme a un temps d’exécution polynomial par rapport à la valeur numérique des données d’entrée, mais pas nécessairement par rapport à la taille réelle de leur représentation. La nuance paraît subtile, mais elle change tout. En informatique théorique, la complexité se mesure normalement en fonction du nombre de bits nécessaires pour écrire l’entrée.
Un algorithme pseudo-polynomial peut donc être efficace lorsque les nombres sont petits, tout en devenant très coûteux lorsque ces nombres augmentent. C’est fréquent dans les problèmes d’optimisation où l’on manipule des poids, des capacités, des coûts, des distances ou des budgets. La question n’est pas seulement “combien d’éléments faut-il traiter ?”, mais aussi “quelle est l’amplitude des valeurs utilisées ?”.
Pour comprendre cette idée, il faut distinguer deux notions : le nombre d’objets fournis à l’algorithme et la taille de leur encodage. Un entier comme 100 tient en peu de bits. Un entier comme 10 000 000 000 en demande davantage, mais pas dix milliards de fois plus. En base binaire, la taille d’un nombre croît selon son logarithme.
C’est cette différence qui rend la complexité pseudo-polynomiale délicate. Un algorithme en O(nW), où n représente le nombre d’objets et W une capacité numérique, semble polynomial si l’on regarde W comme une simple variable. Mais si W est écrit en binaire, la taille de son encodage est de l’ordre de log W. L’algorithme est alors exponentiel par rapport à la taille effective de l’entrée.
Cette distinction est fondamentale dans l’analyse des algorithmes d’optimisation. Elle permet de ne pas confondre une méthode performante en pratique sur certains jeux de données avec une méthode réellement polynomiale au sens strict de la théorie de la complexité.
Le problème du sac à dos illustre parfaitement la notion. On dispose d’un sac ayant une capacité maximale W et d’une liste d’objets, chacun avec un poids et une valeur. L’objectif consiste à choisir les objets qui maximisent la valeur totale sans dépasser la capacité du sac. Ce problème apparaît dans des situations très concrètes : allocation de ressources, choix d’investissements, planification de chargement ou arbitrage budgétaire.
Une solution par programmation dynamique permet de résoudre certaines versions du problème en O(nW). Si W vaut 1 000 et que n vaut 100, le calcul reste raisonnable. Si W vaut 10 milliards, la même approche devient vite irréaliste. Pourtant, le nombre d’objets n’a pas changé. C’est la valeur numérique de la capacité qui fait exploser le temps de calcul.
Cette approche est souvent présentée comme un exemple emblématique d’algorithme pseudo-polynomial. Elle n’est pas “mauvaise” pour autant. Dans de nombreux cas industriels, les capacités sont bornées ou normalisées, ce qui rend la méthode efficace. Mais elle ne constitue pas une preuve que le problème du sac à dos est facile au sens général.
La programmation dynamique est l’un des cadres où la complexité pseudo-polynomiale apparaît le plus souvent. Son principe consiste à décomposer un problème en sous-problèmes plus simples, puis à stocker leurs solutions pour éviter de les recalculer. Cette stratégie est puissante, notamment lorsque les décisions successives dépendent d’un état mesurable, comme une capacité restante ou une somme atteinte.
Dans les problèmes d’optimisation, elle transforme parfois une recherche combinatoire gigantesque en un tableau de calcul maîtrisable. Pour le sac à dos, par exemple, on remplit progressivement une table indexée par les objets et par les capacités possibles. Une présentation pédagogique de cette méthode de décomposition des problèmes d’optimisation aide à comprendre pourquoi elle est si fréquente dans les algorithmes pseudo-polynomiaux.
Mais cette efficacité dépend de la taille du tableau. Si l’état contient une valeur numérique potentiellement très grande, le nombre de cases à calculer augmente avec cette valeur. C’est là que le pseudo-polynomial entre en jeu : la méthode est structurée, rationnelle, souvent très rapide sur des instances modestes, mais elle n’échappe pas toujours à la croissance des grandeurs numériques.
L’expression peut prêter à confusion. Un algorithme pseudo-polynomial ressemble à un algorithme polynomial, mais il ne l’est pas nécessairement au sens théorique. Un véritable algorithme polynomial doit avoir un temps d’exécution borné par un polynôme de la taille de l’entrée, c’est-à-dire du nombre de bits nécessaires pour la décrire.
La différence apparaît clairement avec l’encodage. Si une valeur W est fournie en unaire, par exemple sous forme de W symboles, un algorithme en O(nW) devient polynomial par rapport à la taille de l’entrée. Mais dans les systèmes informatiques réels, les nombres sont généralement encodés en binaire ou en décimal compact. La taille de l’entrée est alors bien plus petite que W lui-même.
C’est pourquoi les chercheurs distinguent les problèmes faiblement NP-difficiles et fortement NP-difficiles. Certains problèmes NP-difficiles admettent des algorithmes pseudo-polynomiaux ; ils sont qualifiés de faiblement NP-difficiles. D’autres restent difficiles même lorsque les valeurs numériques sont bornées ou encodées de manière plus favorable. Cette classification aide à anticiper les stratégies envisageables.
Dans le monde réel, les algorithmes ne sont pas choisis uniquement selon leur pire cas théorique. Un planificateur de production, un outil d’aide à la décision ou un logiciel de gestion de stocks doit surtout répondre à des contraintes précises : taille habituelle des données, délais acceptables, ressources disponibles et qualité attendue de la solution.
Un algorithme pseudo-polynomial peut être parfaitement pertinent si les valeurs manipulées restent limitées. Par exemple, si une entreprise raisonne en unités de palettes, de minutes ou de lots standardisés, les capacités et les coûts peuvent rester dans des bornes raisonnables. La programmation dynamique devient alors une option robuste et explicable.
À l’inverse, si les valeurs sont très grandes ou très détaillées, il faut parfois préférer des méthodes approchées, des heuristiques ou des algorithmes d’approximation. Les méthodes gloutonnes, par exemple, prennent des décisions locales rapides, mais elles ne garantissent pas toujours l’optimum ; leurs limites sont bien illustrées par l’analyse des choix locaux en optimisation.
Le problème de la somme de sous-ensemble est un autre cas classique. On reçoit une liste d’entiers et l’on cherche à savoir s’il existe un sous-ensemble dont la somme atteint une valeur cible S. Une approche par programmation dynamique peut résoudre le problème en temps O(nS). Là encore, l’algorithme dépend directement de la valeur numérique de S, et non seulement de la longueur de son encodage.
On retrouve des phénomènes similaires dans certains problèmes de planification, de découpe, d’équilibrage de charges ou d’allocation de ressources. Dès qu’un état de calcul est indexé par un coût, un poids, une capacité ou un niveau de consommation, la frontière entre efficacité pratique et explosion numérique doit être surveillée.
Il ne faut toutefois pas généraliser à tous les algorithmes d’optimisation. Certains algorithmes de graphes, comme ceux qui calculent des plus courts chemins sous des hypothèses précises, ont des complexités polynomiales classiques. Pour situer cette différence, l’exemple du calcul de chemins optimaux dans un graphe montre une autre famille d’algorithmes, où la structure du graphe joue un rôle central.
Un premier indice consiste à regarder les variables présentes dans la complexité annoncée. Si le temps d’exécution dépend d’une valeur numérique comme W, S, C ou B, il faut se demander si cette valeur représente une quantité réelle ou la taille de son encodage. Une complexité en O(nW), O(nS) ou O(nC) mérite donc un examen attentif.
Le deuxième réflexe est d’observer les tableaux ou structures de données utilisés. Si l’algorithme construit une table dont les colonnes correspondent à toutes les capacités possibles de 0 à W, il y a de fortes chances qu’il soit pseudo-polynomial. Ce n’est pas un défaut en soi, mais une information importante pour prévoir son comportement.
Enfin, il faut tester l’algorithme sur des ordres de grandeur réalistes. Une méthode peut passer sans difficulté de 100 à 10 000 objets si les valeurs restent petites, mais s’effondrer avec seulement 50 objets si les capacités atteignent plusieurs milliards. La complexité pseudo-polynomiale rappelle ainsi que l’échelle numérique des données compte autant que leur quantité.
La complexité pseudo-polynomiale désigne une situation intermédiaire : l’algorithme est souvent bien plus exploitable qu’une recherche exhaustive, mais il ne bénéficie pas des garanties d’un algorithme polynomial classique. Il peut être très efficace sur des instances bornées, structurées ou discrétisées, et beaucoup moins dès que les valeurs numériques deviennent grandes.
Pour un algorithme d’optimisation, cette notion aide à poser les bonnes questions. Les valeurs d’entrée sont-elles petites ? Sont-elles encodées de façon compacte ? Peut-on les arrondir sans perdre trop de précision ? Existe-t-il une approximation fiable si l’optimum exact coûte trop cher ? Ces questions orientent le choix entre programmation dynamique, heuristique, approximation ou méthode exacte plus sophistiquée.
En pratique, comprendre la complexité pseudo-polynomiale permet d’éviter deux erreurs opposées : rejeter trop vite un algorithme utile, ou croire qu’une solution rapide sur de petits exemples restera rapide en toutes circonstances. C’est une notion technique, mais profondément concrète. Elle relie la théorie de la complexité aux contraintes réelles du calcul, là où les nombres ne sont jamais de simples détails.
