NP-completo

Diagramma di Eulero-Venn per le classi di complessità P, NP, NP-Completo e NP-hard

Questa pagina fornisce una descrizione tecnica dei problemi NP-completi. Per una introduzione divulgativa, vedi Classi di complessità P ed NP.

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-completezza

Un problema L è NP-completo se i seguenti enunciati sono veri:

1. L è in NP
2. Per ogni problema L' in NP esiste una riduzione polinomiale di L' in L

Questa è detta Karp-completezza, caso particolare della Cook-completezza che definisce un problema NP-completo se, dato un oracolo per il problema $P$, ovvero un meccanismo in grado di rispondere ad una qualsiasi domanda sull'appartenenza di una stringa a $P$ 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 problemi

Un 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:

• Isomorfismo di grafi: il grafo G₁ è isomorfo al grafo G₂?
• Isomorfismo di sottografi: il grafo G₁ è isomorfo ad un sottografo del grafo G₂?

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:

• Problema di soddisfacibilità dei circuiti booleani (Boolean circuit satisfiability problem, CIRCUIT-SAT)
• Problema di soddisfacibilità booleana (Boolean satisfiability problem, SAT)
• Problema di soddisfacibilità booleana in forma normale congiuntiva (Conjuntive Normal Form Boolean satisfiability problem, CNF-SAT)
• Problema di soddisfacibilità booleana in forma normale congiuntiva con 3 letterali per clausola (3CNF Boolean satisfiability problem, 3-SAT)
• Gioco del quindici (Fifteen puzzle)
• Problema dello zaino (Knapsack problem)
• Problema del ciclo hamiltoniano (Hamiltonian cycle problem)
• Problema del commesso viaggiatore (Traveling salesman problem)
• Problema dell'isomorfismo di sottografi (Subgraph isomorphism problem)
• Problema della somma di sottoinsiemi (Subset sum problem)
• Problema della cricca (Clique problem)
• Problema di copertura dei vertici (Vertex cover problem)
• Problema dell'insieme indipendente (Independent set problem)
• Problema di colorazione dei grafi (Graph coloring problem)

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 imperfette

Fino 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:

• algoritmo di approssimazione: un algoritmo che trova velocemente una soluzione sub-ottimale che si trova in un intorno (noto) di quella ottimale.
• algoritmo probabilistico: un algoritmo il cui tempo medio di esecuzione per una distribuzione data del problema è provata essere buona—idealmente, uno che assegna una bassa probabilità a input "difficili".
• casi speciali: un algoritmo veloce se l'istanza del problema appartiene all'insieme di alcuni casi speciali. La parametrizzazione della complessità può essere vista come una generalizzazione di questo approccio.
• euristica: un algoritmo che funziona "ragionevolmente bene" in molti casi, ma per cui non c'è prova che sia sempre veloce e che dia buoni risultati.

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 riduzione

Nella 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

• Garey, M. and D. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, 1979. ISBN 0716710455 (Questo libro è un classico, che sviluppa la teoria e cataloga molti problemi NPC)
• S. A. Cook, The complexity of theorem proving procedures, Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York, 1971, 151-158
• Paul E. Dunne. An Annotated List of Selected NP-complete Problems. The University of Liverpool, Dept of Computer Science, COMP202.
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger. A compendium of NP optimization problems. KTH NADA. Stockholm.
• Computational Complexity of Games and Puzzles, su ics.uci.edu.
• Tetris is Hard, Even to Approximate, su arxiv.org.
• Minesweeper is NP-complete!, su for.mat.bham.ac.uk. URL consultato l'11 giugno 2006 (archiviato dall'url originale il 16 dicembre 2006).
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Chapter 34: NP-Completeness, pp. 966–1021.
• Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997, ISBN 0-534-94728-X. Sections 7.4–7.5 (NP-completeness, Additional NP-complete Problems), pp. 248–271.
• Christos Papadimitriou, Computational Complexity, 1st edition, Addison Wesley, 1993, ISBN 0-201-53082-1. Chapter 9: NP-complete problems, pp. 181–218.

Voci correlate

• Lista di problemi NP-Completi
• ASR-completi
• Teorema di Ladner