Chaque algorithme ne devrait-il pas fonctionner en temps pseudo-polynomial?

Question

Wiki dit qu'un algorithme numérique s'exécute en temps pseudo-polynomial si son temps d'exécution est polynomial dans la valeur numérique de l'entrée, mais est exponentiel dans la longueur de l'entrée - le nombre de bits requis pour le représenter.

Cette réponse Explique très bien pourquoi l'algorithme de test de primalité du temps d'exécution $ o (n) $ est en fait du temps pseudo-polynomial. Tout simplement Une manière très simple d'y penser est que si vous doublez la limite, la taille de l'entrée ne fait qu'augmente d'un bit (car la limite fait partie de l'entrée), tandis que le temps d'exécution est doublé. C'est un comportement clairement exponentiel par rapport à la taille de l'entrée.

Autrement dit, ajoutez un bit supplémentaire dans la représentation de bit de votre entrée et le temps d'exécution augmentera de façon exponentielle.

Okaaay, mon doute est, n'est-ce pas applicable à chaque algorithme alors? Comme dans le tri. On pourrait dire "La principale différence est que, dans les algorithmes de temps pseudo-polynomiale, N représente un nombre dans l'entrée, tandis que dans d'autres algorithmes (tri) N représente le nombre de choses"

À quoi je pense, comment est-ce important? Recherche maximale dans un tableau non trié de taille $ n $ prend $ o (n) $ de temps, ajoutez un bit supplémentaire à $ n $ et le temps d'exécution augmentera de façon exponentielle. Par conséquent, chaque algorithme ne devrait-il pas fonctionner en temps pseudo-polynomial?