Problema intrattabile

Il problema intrattabile è un problema per il quale non esiste un algoritmo con complessità polinomiale in grado di risolverlo. È errato pensare che il problema intrattabile non abbia soluzione. Il problema intrattabile può avere o meno una soluzione. Ciò che distingue il problema intrattabile dal problema trattabile è l'assenza di un algoritmo computazionale in grado di giungere alla soluzione in tempi di esecuzione accettabili e con un consumo di risorse ( memoria ) accettabile. Un esempio di problema intrattabile è il problema del commesso viaggiatore, per il quale non esiste alcun algoritmo risolutivo con complessità polinomiale ( algoritmo polinomiale ). Un problema intrattabile potrebbe, ad esempio, essere risolvibile mediante algoritmi di complessità esponenziale. Tuttavia, l'elevato consumo di risorse del computer e/o il tempo di esecuzione proibitivo renderebbe l'algoritmo inutile.