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

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.

Definizione formale di NP-completezza

Un problema $\backslash pi$ è NP completo se $\backslash pi\; \backslash in$NP e se $\backslash forall\; \backslash pi^\text{'},\; \backslash pi^\text{'}\; \backslash le\; \backslash pi$

Ovvero se $\backslash pi$ è 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

"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 è sufficente 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ù dificile. 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.

Matematica||Informatica teorica||Teoria della complessità