Problemi NP completi

I problemi NP-completi sono sia problemi NP che NP-difficili (NP-hard).

I problemi NP-completi sono una categoria di problemi di decisione che soddisfano due condizioni principali:

• Sono problemi NP perché una soluzione proposta può essere verificata come corretta o meno in tempo polinomiale rispetto alla dimensione dell'input.
• Sono problemi NP-difficili perché sono almeno tanto difficili quanto il problema più difficile in NP.

Questo vuol dire che se si trovasse un modo per risolvere un problema NP-completo in tempo polinomiale, allora tutti i problemi in NP potrebbero essere risolti in tempo polinomiale.

Per questa ragione sono particolarmente importanti nella teoria computazionale.

Esempio

Un altro classico esempio di problema NP-completo è il problema del commesso viaggiatore (Travelling Salesman Problem, TSP).

Nel TSP, ci viene dato un insieme di città e la distanza tra ogni coppia di città, e dobbiamo trovare il percorso più breve che visita ogni città esattamente una volta e ritorna alla città di partenza.

La sfida sta nel fatto che il numero di percorsi possibili cresce in modo fattoriale all'aumentare del numero delle città, rendendo impraticabile l'esplorazione esaustiva di tutte le possibilità per insiemi grandi di città.

Nonostante ciò, se ci viene fornito un percorso specifico, possiamo facilmente calcolare la sua lunghezza totale e verificare se visita tutte le città una volta sola, soddisfacendo così il criterio di appartenenza a NP.

Trovare il percorso ottimale (o dimostrare che un percorso dato è il migliore possibile) è estremamente difficile, ma la verifica di un percorso candidato è relativamente semplice, caratteristiche che lo definiscono come NP-completo.