NP-Completo

Da Wikipedia, l'enciclopedia libera.

Questa voce riguardante un argomento di informatica non è ancora stata tradotta completamente dalla lingua inglese. Terminala o riscrivila tu. Nota: il testo da tradurre potrebbe essere nascosto: vai in modifica per visualizzarlo.

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

[modifica] Introduzione

Nella Teoria della Complessità i problemi NP-completi sono i più difficili problemi in NP ("problemi non deterministici a tempo polinomiale") nel senso che quasi sicuramente non appartengono a P. La ragione è che, se si potesse trovare un algoritmo in grado di risolvere velocemente (cioè in tempo polinomiale) un qualsiasi problema NP-completo, allora si potrebbe usarlo per risolvere velocemente tutti i problemi 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 sottoinsiemi.

[modifica] Definizione formale di NP-completezza

Un problema π è NP completo se NP e se

Ovvero se π è il piu difficile problema in NP.

In altre parole possiamo dire che un linguaggio L è NP-completo se i seguenti enunciati sono veri:

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

questa è detta in particolare Karp-completezza, si può dire sia un 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, è possiblile 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-complete è sufficiente mostrare che un problema NP-complete già conosciuto si riduce a 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-complete" 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 successivamete, 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 problemi NP-completi sono infatti risolvibili in tempo polinomiale, facendo di questo uno dei più grandi problemi della matematica. Comunque, c'è il forte sospetto fra gli scienziati che questi problemi non possono essere risolti in tempo polinomiale; secondo una votazione informale nel 2002 fra 100 ricercatori, 61 di loro dissero che P≠NP,, a confronto che soli 9 che dissero 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 che 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 soddisfattibilità 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 soddisfattibilità 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.

[modifica] 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 è 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 è 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).

• Boolean satisfiability problem (SAT)
• Fifteen puzzle
• Knapsack problem
• Hamiltonian cycle problem
• Traveling salesman problem
• Subgraph isomorphism problem
• Subset sum problem
• Clique problem
• Vertex cover problem
• Independent set problem
• Graph coloring problem

Per un elenco più completo di problemi NP-completi vedi Lista 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.

Immagine:Relative NPC chart.PNG

Di solito vi son piccole differenze tra problemi in P e problemi NP-completi. Per esempio il 3-SAT, una riduzione del problema di soddisfacibilità booleano, rimane NP-Completo, nonostante il problema 2SAT, che è leggermente meno stringente sia in P.

[modifica] 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 parametrizzazzione 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 sub-ottimale O(n log n) usato per il problema della colorazione del grafo 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 hanno un gran numero di registri generici, anche un approccio euristico è efficace per questa applicazione.

[modifica] Vedi Anche

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

[modifica] 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
• Tetris is Hard, Even to Approximate
• Minesweeper is NP-complete!
• 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 0201530821 Chapter 9: NP-complete problems, pp.181–218.