Abbiamo scritto su algoritmi efficienti per risolvere problemi complessi, come il percorso più breve, il grafico di Eulero, l’albero di spanning minimo, ecc. Quelle erano tutte storie di successo di progettisti di algoritmi. In questo post, storie di fallimento di informatica sono discussi.
Tutti i problemi computazionali possono essere risolti da un computer? Ci sono problemi computazionali che non possono essere risolti dagli algoritmi anche con un tempo illimitato. Ad esempio, Turing Interrompe il problema (dato un programma e un input, se il programma alla fine si fermerà quando verrà eseguito con quell’input o verrà eseguito per sempre). Alan Turing ha dimostrato che l’algoritmo generale per risolvere il problema di arresto per tutte le possibili coppie di input del programma non può esistere. Una parte fondamentale della dimostrazione è che la macchina di Turing è stata utilizzata come definizione matematica di un computer e di un programma (problema di interruzione della fonte).
Lo stato dei problemi NP completi è un’altra storia di fallimento, i problemi NP completi sono problemi il cui stato è sconosciuto. Nessun algoritmo del tempo polinomiale è stato ancora scoperto per qualsiasi problema NP completo, né nessuno è ancora stato in grado di dimostrare che non esiste un algoritmo del tempo polinomiale per nessuno di essi. La parte interessante è che se uno qualsiasi dei problemi NP completi può essere risolto in tempo polinomiale, allora tutti possono essere risolti.
Quali sono i problemi NP, P, NP-complete e NP-Hard?
P è un insieme di problemi che possono essere risolti da una macchina di Turing deterministica in tempo polinomiale.
NP è un insieme di problemi decisionali che possono essere risolti da una macchina di Turing non deterministica in tempo polinomiale. P è sottoinsieme di NP (qualsiasi problema che può essere risolto dalla macchina deterministica in tempo polinomiale può anche essere risolto dalla macchina non deterministica in tempo polinomiale).
Informalmente, NP è un insieme di problemi decisionali che possono essere risolti da un tempo polinomiale tramite un “Algoritmo fortunato”, un algoritmo magico che fa sempre una giusta ipotesi tra l’insieme di scelte dato (Fonte Ref 1).
I problemi NP-completi sono i problemi più difficili nel set NP. Un problema decisionale L è NP-completo se:
1) L è in NP (Qualsiasi soluzione data per problemi NP-completi può essere verificata rapidamente, ma non esiste una soluzione nota efficiente).
2) Ogni problema in NP è riducibile a L in tempo polinomiale (La riduzione è definita di seguito).
Un problema è NP-Difficile se segue la proprietà 2 menzionata sopra, non ha bisogno di seguire la proprietà 1. Pertanto, NP-Complete set è anche un sottoinsieme di NP-Hard set.
Decisione vs Problemi di ottimizzazione
NP-completezza si applica al regno dei problemi decisionali. È stato impostato in questo modo perché è più facile confrontare la difficoltà dei problemi decisionali rispetto a quella dei problemi di ottimizzazione. In realtà, però, essere in grado di risolvere un problema di decisione in tempo polinomiale spesso ci permetterà di risolvere il problema di ottimizzazione corrispondente in tempo polinomiale (usando un numero polinomiale di chiamate al problema di decisione). Quindi, discutere la difficoltà dei problemi decisionali è spesso equivalente a discutere la difficoltà dei problemi di ottimizzazione. (Fonte Ref 2).
Ad esempio, considera il problema della copertura dei vertici (dato un grafico, scopri il set di vertici di dimensioni minime che copre tutti i bordi). È un problema di ottimizzazione. Il problema di decisione corrispondente è, dato il grafico G e k non orientato, esiste una copertura del vertice della dimensione k?
Che cos’è la riduzione?
L1 e L2 siano due problemi decisionali. Supponiamo che l’algoritmo A2 risolva L2. Cioè, se y è un input per L2, l’algoritmo A2 risponderà Sì o No a seconda che y appartenga a L2 o meno.
L’idea è di trovare una trasformazione da L1 a L2 in modo che l’algoritmo A2 possa essere parte di un algoritmo A1 per risolvere L1.
La riduzione dell’apprendimento in generale è molto importante. Ad esempio, se abbiamo funzioni di libreria per risolvere determinati problemi e se possiamo ridurre un nuovo problema a uno dei problemi risolti, risparmiamo molto tempo. Considera l’esempio di un problema in cui dobbiamo trovare il percorso minimo del prodotto in un dato grafico diretto in cui il prodotto del percorso è la moltiplicazione dei pesi dei bordi lungo il percorso. Se abbiamo il codice per l’algoritmo di Dijkstra per trovare il percorso più breve, possiamo prendere il registro di tutti i pesi e usare l’algoritmo di Dijkstra per trovare il percorso minimo del prodotto piuttosto che scrivere un nuovo codice per questo nuovo problema.
Come dimostrare che un dato problema è NP completo?
Dalla definizione di NP-completo, sembra impossibile dimostrare che un problema L è NP-Completo. Per definizione, ci richiede di mostrare che ogni problema in NP è il tempo polinomiale riducibile a L. Fortunatamente, c’è un modo alternativo per dimostrarlo. L’idea è di prendere un problema NP-Completo noto e ridurlo a L. Se la riduzione del tempo polinomiale è possibile, possiamo dimostrare che L è NP-Completo per transitività di riduzione (Se un problema NP-Completo è riducibile a L in tempo polinomiale, allora tutti i problemi sono riducibili a L in tempo polinomiale).
Qual è stato il primo problema dimostrato come NP-Completo?
Ci deve essere un primo problema NP-Completo dimostrato dalla definizione di problemi NP-Completi. SAT (Boolean satisfiability problem) è il primo problema NP-Completo dimostrato da Cook (vedi il libro CLRS per la prova).
È sempre utile conoscere NP-Completezza anche per gli ingegneri. Supponiamo che ti venga chiesto di scrivere un algoritmo efficiente per risolvere un problema estremamente importante per la tua azienda. Dopo un sacco di pensiero, puoi solo trovare un approccio esponenziale al tempo che non è pratico. Se non conosci NP-Completezza, puoi solo dire che non potrei venire con un algoritmo efficiente. Se conosci NP-Completezza e dimostra che il problema è NP-completo, puoi dire con orgoglio che è improbabile che la soluzione del tempo polinomiale esista. Se esiste una soluzione di tempo polinomiale possibile, allora quella soluzione risolve un grosso problema di informatica che molti scienziati hanno provato per anni.
Discuteremo presto più problemi NP-Completi e la loro prova di NP-Completezza.