OKPEDIA ALGORITMO

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.

https://www.okpedia.it/problema_intrattabile




Questo sito utilizza cookie tecnici. Sono presenti alcuni cookie di terzi ( Gooogle, Facebook ) per la personalizzazione degli annunci pubblicitari. Cliccando su OK, scorrendo la pagina o proseguendo la navigazione in altra maniera acconsenti all’uso dei cookie.

Per ulteriori informazioni o per revocare il consenso fai riferimento alla Privacy del sito.