Les algorithmes qui jouent sur la taille des nombres

Un algorithme pseudo-polynomial est un cas fascinant où la complexité dépend de la *valeur* des nombres en entrée, pas de leur *taille mémoire*. Concrètement : si tu dois trier des nombres, un algo polynomial standard le fait en temps proportionnel au nombre d'éléments. Un algo pseudo-polynomial, lui, pourrait prendre plus de temps si les nombres eux-mêmes deviennent énormes. C'est utile pour certains problèmes NP-complets qui deviennent soudain solubles quand les chiffres restent "raisonnables". Un concept clé pour comprendre où s'arrêtent les vraies limites du calcul.