Problema trattabile

Un problema trattabile è un problema che può essere risolto computazionalmente mediante un algoritmo efficiente. L'algoritmo è efficiente quando il tempo di esecuzione è limitato superiormente da una funzione polinomiale n^k dove k è un numero intero positivo. Viceversa, nel caso in cui non sia possibile risolvere computazionalmente il problema, quest'ultimo viene detto problema intrattabile. Dal punto di vista computazionale la soluzione a un problema trattabile può essere trovata in vari modi. La teoria della complessità si occupa di analizzare tutte le possibilità ( algoritmi ) al fine di individuare l'algoritmo efficiente ossia quello in grado di trattare e risolvere il problema in meno tempo e/o con minore consumo di risorse.