L’argomento viene trattato in modo molto semplificato.
Definiamo polinomiali quei problemi con
e esponenziali quelli con
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.
Tra questi problemi (commesso viaggiatore, zaino, …) 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.
Se dovesse esistere un algoritmo polinomiale per uno qualsiasi tra essi questo potrebbe essere utilizzato anche per tutti gli altri.
Problemi intrattabili
Ci sono problemi per i quali si può dimostrare che il tempo di esecuzione del miglior algoritmo è almeno esponenziale
- torre di Hanoi
- permutazioni
- …
Si dice che sono problemi intrinsecamente esponenziali.
Sono problemi intrattabili per la maggior parte delle loro istanze.