L’argomento viene trattato in modo molto… semplificato.
Definiamo polinomiali quei problemi con T(n) <= nc, (c > 1) e esponenziali quelli con T(n) <= an, (a > 1).
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.
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 polinomiali non deterministici (NP)
Insiemisticamente, P ( NP ( EXP
Osserva
- si sceglie uno di questi problemi, per esempio il commesso viaggiatore, e si dichiara NP Completo, NP-C
- dato un problema NP si possono trasformare i suoi dati input e output e utilizzare l’algoritmo risolutivo di un altro problema NP-C già noto
- se dovesse esistere un algoritmo polinomiale per un qualsiasi problema NP-C potrebbe essere utilizzato per tutti gli NP-C…