Problemi difficili
Definiamo polinomiali quei problemi con
T(n) <= nc, (c > 1)
e esponenziali quelli con
T(n) <= an, (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
- commesso viaggiatore
- zaino
- ...
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 esponenzialeSi dice che sono problemi intrinsecamente esponenziali.
Sono problemi intrattabili per la maggior parte delle loro istanze.
