|
NP-completo
Nella teoria della complessità computazionale i problemi NP-completi sono i più difficili problemi nella classe NP ("problemi risolvibili non-deterministicamente in tempo polinomiale") nel senso che, se si trovasse un algoritmo in grado di risolvere "velocemente" (nel senso di utilizzare tempo polinomiale) un qualsiasi problema NP-completo, allora si potrebbe usarlo per risolvere "velocemente" ogni problema in NP. La classe di complessità che contiene tutti i problemi NP-completi è spesso indicata con NP-C. Un esempio di problema NP-completo è il problema delle somme parziali, cioè: dato un insieme finito di numeri interi, determinare se esiste un sottoinsieme tale che la somma dei suoi elementi sia zero. È evidente che è facile verificare velocemente se un sottoinsieme è o meno una soluzione del problema, ma non è noto alcun metodo per trovare una soluzione che sia sensibilmente più veloce di provare tutti i possibili sottoinsiemi tranne i due che contengono tutti numeri concordi (tutti negativi o tutti positivi), quelli formati da un solo numero negativo e da tutti numeri positivi maggiori in valore assoluto al numero negativo e quelli formati da un solo numero positivo e da tutti numeri negativi maggiori in valore assoluto al numero positivo. Definizione formale di NP-completezzaUn problema L è NP-completo se i seguenti enunciati sono veri:
Questa è detta Karp-completezza, caso particolare della Cook-completezza che definisce un problema NP-completo se, dato un oracolo per il problema , ovvero un meccanismo in grado di rispondere ad una qualsiasi domanda sull'appartenenza di una stringa a in un'unità di tempo, è possibile riconoscere in tempo polinomiale un qualsiasi linguaggio in NP. La definizione di Cook-completezza risulta essere più generale tanto da includere i complementi dei problemi NP-completi nella classe dei problemi NP-completi. "Riducibile" qui significa che per ogni problema L c'è una riduzione polinomiale, un algoritmo deterministico che trasforma istanze l ∈ L in istanze c ∈ C, così che la risposta a c è sì se e solo se la risposta a l è sì. Per provare che un problema NP A è infatti un problema NP-completo è sufficiente mostrare che un problema NP-completo già conosciuto si riduce ad A. Una conseguenza di questa definizione è che se avessimo un algoritmo di tempo polinomiale per C, potremmo risolvere tutti i problemi in NP in tempo polinomiale. Questa definizione è stata data da Stephen Cook in una pubblicazione intitolata 'The complexity of theorem-proving procedures' alle pagine 151-158 di Proceedings of the 3rd Annual ACM Symposium on Theory of Computing nel 1971, anche se il termine NP-completo non appare da nessuna parte nel suo scritto. A quella conferenza di computer science, ci fu un acceso dibattito tra gli scienziati dell'informazione sul tema se problemi NP-completi potessero essere risolti in tempo polinomiale con una macchina di Turing deterministica. John Hopcroft convinse tutti i presenti alla conferenza ad accantonare questa questione per riprenderla successivamente, visto che nessuno aveva prove formali per dimostrare quello che diceva. Questa questione è nota come il problema se P=NP. Nessuno ancora è stato capace di provare se i problemi NP-completi siano infatti risolvibili in tempo polinomiale, facendo di questo uno dei più grandi problemi della matematica. C'è comunque il forte sospetto fra gli scienziati che questi problemi non possano essere risolti in tempo polinomiale; secondo una votazione informale nel 2002 fra 100 ricercatori, per 61 di loro parve più verosimile che P≠NP mentre solo per 9 che P=NP. Il Clay Mathematics Institute a Cambridge, MA offre la ricompensa di un milione di dollari a chiunque riesca a fornire una dimostrazione che P=NP o P≠NP. All'inizio sembra abbastanza sorprendente che problemi NP-completi debbano perfino esistere, ma nel celebre teorema di Cook-Levin (dimostrato indipendentemente da Leonid Levin), Cook provò che il problema della soddisfacibilità booleana è NP-completo. Nel 1972 Richard Karp provò che alcuni altri problemi erano lo stesso NP-completi, quindi c'è una classe di problemi NP-completi (oltre il problema della soddisfacibilità booleana). Dal risultato originale di Cook, migliaia di altri problemi sono stati mostrati essere NP-completi; molti di questi problemi sono riportati nel libro di Garey e Johnson's 1979 Computers and Intractability: A Guide to NP-Completeness. Un problema che soddisfa la condizione 2 ma non necessariamente la condizione 1 è detto NP-hard. Informalmente, un problema NP-hard è "almeno difficile come" qualsiasi problema NP-completo, e forse anche più difficile. Per esempio, scegliere la mossa perfetta in certi giochi da tavolo di lato arbitrario è NP-hard o perfino strettamente più difficile di problemi NP-hard. Esempi di problemiUn esempio interessante è il problema di isomorfismo di grafi, il problema della teoria dei grafi che consiste nel determinare se esiste un isomorfismo tra due grafi. Due grafi sono isomorfi se uno può essere trasformato nell'altro semplicemente rinominando i suoi vertici. Consideriamo questi due problemi:
Il problema dell'isomorfismo di sottografi è NP-completo. Si sospetta che il problema dell'isomorfismo di grafi non sia né P né NP-completo, sebbene sia evidentemente in NP. Questo è un esempio di un problema che si ritiene computazionalmente difficile, ma che si ritiene non sia NP-completo. Il metodo più facile per dimostrare che un nuovo problema sia NP-completo è prima di tutto dimostrare che appartiene alla classe NP, e quindi trovare una riduzione da un problema che si sa essere NP-completo al nuovo problema (nella sua forma decisionale). Di seguito si indicano alcuni famosi problemi NP-completi, con accanto il nome in lingua inglese e la relativa sigla:
Per un elenco più completo di problemi NP-completi vedi Lista di problemi NP-completi. Segue uno schema di alcuni problemi e delle riduzioni tipicamente utilizzate per provarne la NP-completezza. Nello schema una freccia da un problema ad un altro indica la direzione della riduzione. Di solito vi sono piccole differenze tra problemi in P e problemi NP-completi. Per esempio il 3-SAT, una riduzione del problema di soddisfacibilità di formule booleane, rimane NP-completo, nonostante il problema 2SAT, che è leggermente meno stringente sia in P. Soluzioni imperfetteFino ad ora, tutti gli algoritmi conosciuti per problemi NP-Completi necessitano di un tempo superpolinomiale nella dimensione dell'input. L'esistenza di algoritmi più veloci è sconosciuta. Quindi, per risolvere un problema NP-Completo di dimensioni non banali, generalmente vengono utilizzati i seguenti approcci:
Un esempio di algoritmo euristico è l'algoritmo greedy ("algoritmo ingordo") sub-ottimale O(n log n) usato per il problema della colorazione dei grafi durante la fase di allocazione dei registri di alcuni compilatori. Ogni vertice è una variabile, gli archi vengono disegnati tra le variabili usate nello stesso momento, e i colori indicano il registro assegnato ad ogni variabile. Poiché la maggior parte delle macchine RISC ha un gran numero di registri generici, anche un approccio euristico è efficace per quest'applicazione. Completezza con diversi tipi di riduzioneNella definizione di NP-completezza data sopra, il termine "riduzione" è stato usato nel suo significato tecnico di riduzione molti a uno in tempo polinomiale. Un altro tipo di riduzione è la riduzione di Turing in tempo polinomiale. Dati due problemi X e Y e data una procedura f che risolve Y in tempo polinomiale, si parla di riduzione di Turing con tempo polinomiale se è possibile scrivere un programma che richiami f e risolva X in tempo polinomiale. Questa definizione di riducibilità è in contrasto con la riducibilità molti a uno. In quest'ultima, infatti, il programma può richiamare la procedura una sola volta e il valore restituito dalla procedura deve essere il valore restituito dal programma. Se si definisse un concetto analogo alla NP-completezza utilizzando le riduzioni di Turing invece che quelle molti a uno, l'insieme dei problemi non sarebbe più piccolo dell'insieme di quelli NP-completi. Non è ancora chiaro se esso sarebbe invece, più grande. Se i due concetti fossero uguali, allora ne seguirebbe che NP = co-NP. Poiché per definizione l'insieme di problemi NP-completi e il suo complementare sono uguali considerando la riducibilità di Turing e poiché i due insiemi sono entrambi sovrainsiemi degli stessi insiemi definiti con le riduzioni molti a uno. Perciò, se entrambe le definizioni di NP-completezza sono uguali, c'è un problema co-NP-completo (sotto entrambe le definizioni) come ad esempio il complemento del problema della soddisfacibilità booleana che è anche un problema NP-completo (sotto entrambe le definizioni). Questo implicherebbe che NP = co-NP come si vede nella dimostrazione dell'articolo co-NP. Anche se l'uguaglianza di NP e co-NP è una questione aperta è considerata improbabile, e quindi è altrettanto improbabile che le due definizione di NP-completezza siano equivalenti. Un altro tipo di riduzione che viene spesso usato per definire l'NP-completezza è la riduzione molti a uno in spazio logaritmico. Essa è una riduzione molti a uno che può essere calcolata usando una quantità di spazio al più logaritmica. Dato che ogni computazione che può essere fatta in uno spazio logaritmico può anche essere fatta in tempo polinomiale, ne segue che se esiste una riduzione molti a uno in spazio logaritmico esiste anche una riduzione molti a uno in tempo polinomiale. Questo tipo di riduzione è più raffinata della più comune riduzione molti a uno in tempo polinomiale e permette di distinguere più classi di problemi come ad esempio la classe dei problemi P-completi. Se sotto questo tipo di riduzione cambi la definizione di NP-completezza è ancora una domanda aperta. Bibliografia
Voci correlateAltri progetti
Collegamenti esterni
|
