Ogni algoritmo non dovrebbe funzionare nel tempo pseudo-polinomiale?

Question

Wiki afferma che un algoritmo numerico funziona in tempo pseudo-polinomiale se il suo tempo di esecuzione è polinomiale nel valore numerico dell'input, ma è esponenziale nella lunghezza dell'input-il numero di bit richiesti per rappresentarlo.

Questa risposta Spiega molto bene perché l'algoritmo di test di primalità del tempo di esecuzione $ o (n) $ è in realtà tempo pseudo-polinomiale. Semplicemente Un modo molto semplice di pensarci è che se si raddoppia il limite, la dimensione dell'input aumenta solo di un bit (poiché il limite fa parte dell'input), mentre il tempo di esecuzione è raddoppiato. Questo è chiaramente un comportamento esponenziale rispetto alla dimensione dell'input.

Cioè, aggiungi un bit in più nella rappresentazione di bit del tuo input e il tempo di esecuzione aumenterà in modo esponenziale.

Okaaay, il mio dubbio è: allora non è applicabile a ogni algoritmo? Come nel smistamento. Uno potrebbe dire "La differenza principale è che, negli algoritmi del tempo pseudo-polinomiale, N rappresenta un numero nell'input, mentre in altri algoritmi (ordinamento) N rappresenta il numero di cose"

A che penso, come è importante? La ricerca del massimo in una serie non eseguita di dimensioni $ n $ prende $ o (n) $ tempo, aggiungi un bit in più a $ n $ e il tempo di esecuzione crescerà in modo esponenziale. Quindi ogni algoritmo non dovrebbe funzionare nel tempo pseudo-polinomiale?