Le sac à dos, et le mot « pseudo »

1. L'entrée est constituée de $n$ objets et de la capacité $C$ ; sa taille est $\Theta (n\log C)$ bits environ. Un coût $\Theta (nC)$ est donc exponentiel en la taille : doubler le nombre de bits de $C$ élève $C$ au carré.

2. Le temps est multiplié par $10$, alors que l'entrée n'a grossi que de $3$ ou $4$ bits. Mesuré, à $n=20$ objets fixés :

Dix bits de plus, huit cents fois plus de temps. La croissance est linéaire en $C$, donc exponentielle en la taille de $C$ : c'est la définition même de pseudo-polynomial.

3. On l'emploie quand $C$ est réellement petit — c'est-à-dire quand l'instance vient d'une situation où les capacités sont bornées par une constante du problème, et non par la place mémoire. Un sac de $50$ kg à $100$ g près donne $C=500$ : la table tient. Une somme d'argent au centime près sur des millions d'euros donne $C=10^8$ : elle ne tient plus.

La leçon générale. « Pseudo-polynomial » n'est pas une nuance de vocabulaire : c'est la différence entre un algorithme qui passe à l'échelle et un qui ne passe pas, et elle ne se voit que si l'on compte la taille en bits. C'est aussi la première ligne du tableau du chapitre : quand un paramètre reste petit, on a le droit d'être pseudo-polynomial.