Definiamo polinomiali quei problemi con

T(n) <= n^c, (c > 0)

ed esponenziali quelli con

T(n) <= aⁿ, (a > 1)

Esistono molti problemi che ammettono un algoritmo risolutivo esponenziale ma per i quali non si è certi che la loro complessità sia esponenziale e si spera che in futuro possano essere ricondotti nella classe dei polinomiali. Si definiscono problemi non polinomiali (NP), insiemisticamente:

P ( NP ( EXP

Tra questi problemi

esiste una relazione sorprendente: sono tutti equivalenti tra loro.

Ogni volta che è stato introdotto un nuovo problema tra gli NP è stato dimostrato che, a meno di qualche "adattamento", la sua soluzione può essere ricavata a partire dalle soluzioni di un altro problema già noto come NP.

Ma allora se dovesse esistere un algoritmo polinomiale per uno qualsiasi tra essi questo potrebbe essere utilizzato anche per tutti gli altri!

Ci sono problemi per i quali si può dimostrare che il tempo di esecuzione del miglior algoritmo è almeno esponenziale

Si dice che sono problemi intrinsecamente esponenziali. Sono di fatto non risolvibili per la maggior parte delle loro istanze.