Riduzione polinomiale

Enciclopedia della Scienza e della Tecnica (2008)

riduzione polinomiale

Fabrizio Luccio

Nello studio della complessità di algoritmi combinatori l’attenzione è focalizzata sulla classificazione dei problemi come polinomiali o esponenziali. L’esame si può limitare alla versione decisionale che è il nucleo di complessità di un problema e si propone di stabilire se il dato d’ingresso ha o meno una determinata proprietà, ovvero costituisce o meno una soluzione. Trattando, per es., di grafi i due problemi decisionali del ciclo euleriano e del ciclo hamiltoniano chiedono di stabilire se un grafo arbitrario G contiene un percorso chiuso che attraversa esattamente una volta tutti gli spigoli (ciclo euleriano) o tutti i vertici (ciclo hamiltoniano). Si definiscono la classe P come quella di tutti i problemi per i quali la decisione richiesta può essere presa in tempo polinomiale nella dimensione dei dati, e la classe NP come quella di tutti i problemi per cui tale decisione può richiedere tempo esponenziale ma è possibile verificare in tempo polinomiale che una soluzione proposta ha le caratteristiche desiderate. Il problema del ciclo euleriano appartiene a P, cioè si può decidere in tempo polinomiale se esiste un ciclo euleriano in C; quello del ciclo hamiltoniano appartiene a NP perché è possibile verificare in tale tempo che un dato ciclo è hamiltoniano, anche se determinarne l’esistenza dove non sia dato richiede tempo esponenziale. Si ha P⊆NP. Il meccanismo di riduzione polinomiale consente di stabilire la difficoltà dei problemi in NP, nel senso seguente. Un problema P1 si riduce in tempo polinomiale a un problema P2, in formule P1PP2, se esiste una funzione f calcolabile in tempo polinomiale tale che X è una soluzione di P1 se e solo se f(X) è una soluzione di P2. Conoscendo un algoritmo A di soluzione per P2 e la funzione f relativa alla coppia P1, P2, si può risolvere P1 trasformando ogni dato X di P1 in un dato f(X) di P2 e applicando l’algoritmo A a f(X). Ne segue che se P2 appartiene a P anche P1 appartiene a P. I problemi ‘più difficili’ in NP sono pertanto così definiti: un problema P è NP-completo se P∈NP e P′≤PP per ogni P′∈NP.

Complessità algoritmica

CATEGORIE
TAG

Ciclo hamiltoniano

Se e solo se

Algoritmo

Grafo