Cos’è un problema NP-completo?
Un problema NP-completo è un problema algoritmico per cui non è stata trovata una soluzione efficiente, tuttavia nessuno ha dimostrato che non possa esistere un algoritmo efficiente per questo tipo di problemi (la dimostrazione di una soluzione un problema NP-completo implicherebbe l’esistenza di una soluzione efficiente per tutta la classe di problemi).
- I problemi NP-completi sono simili tra di loro: una piccola variazione nella definizione del problema può causare una grande variazione dell’efficienza dell’algoritmo utilizzato.
L'importanza di riconoscere un problema NP-completo.
E’ molto importante riconoscere questo tipo di problemi altrimenti si rischia di utilizzare più tempo del necessario nella ricerca della soluzione migliore: tornano utili la gli algoritmi di riduzione.
- In questa classe di problemi è buona norma utilizzare una buona soluzione piuttosto che la migliore possibile (vedi Problema del commesso viaggiatore).