Calcolabilità e Complessità : riduzione tra problemi

Utente Junior Età : 21 Registrato il : 23/01/08 Messaggi : 341

Partiamo subito con la definizione formato soft.
Dati L1 e L2, diciamo che L1 è riducibile polinomialmente a L2 (<=p, purtroppo il pedice non si può fare o non lo so fare io, quindi abbiate pazienza, userò l'italiano al posto dei simboli) se esiste un algoritmo f(), o trasformazione, calcolabile in tempo polinomiale.
Così se abbiamo una stringa w appartenente a L1 e L2 è il linguaggio di cui sappiamo la membership (cioè a quale classe appartiene), tramite questa funzione f() possiamo stabilire se f(w) appartiene a L2.
In parole povere questa funzione "crea" una nuova stringa appartenente al linguaggio noto, in questo caso L2, così se il risultato di f(w) appartiene alla classe di L2, allora anche w apparterrà alla stessa classe. Abbiamo quindi fatto una trasformazione da un problema ignoto ad uno noto.

Esempio pratico.
Abbiamo un algoritmo A per L2 e dobbiamo vedere se w appartiene a L1.
Alla funzione f() passeremo quindi w per far si che questa la trasformi ad hoc per L2:
w -> f(w) -> A(f(w))
Questo disegnino vuol dire che passeremo all'algoritmo A la trasformazione di w tramite f(). Se A(f(w)) è un'istanza si, cioè se f(w) appartiene a L2, allora w apparterrà a L1. Analogamente, se A(f(w)) è un'istanza no, cioè se f(w) non appartiene a L2, allora nemmeno w apparterrà a L1.

Poiché la funzione f() è polinomiale, se l'algoritmo A è polinomiale A(f(w)) lo risolviamo in tempo polinomiale. Tutto il complesso sarà ancora polinomiale, quindi il costo di trasformazione è polinomiale in w, cioè nell'input di partenza.

Da questo ricaviamo un teorema:
TH. Se L1 è riducibile polinomialmente a L2 e L2 appartiene a P, allora L1 appartiene a P.

Il bello di questo teorema è che vale anche per i problemi NP-COMPLETE.
TH. Se P1 è un problema NP-COMPLETE e P2 è un problema in NP. se esiste una riduzione polinomiale da P1 a P2, allora P2 è NP-COMPLETE.

Questi due teoremi sono dimostrabili e dimostrati, ovviamente, e ovviamente tenterò di riproporli qui!

Cominciamo col primo:
se L1 è riducibile polinomialmente a L2 e L2 appartiene a P, allora L1 appartiene a P.
Poiché A lavora con f(w), l'output di f() quanto può essere diventato grande rispetto a w? Quale è la size di f(w), cioè |f(w)|?
Supponiamo che l'algoritmo A per L2 ci metta O(n^(kA)) passi e che O(n^(kf)) sia il massimo numero di passi che deve fare f(). Se consideriamo la stringa w di cui parlavamo prima, allora il massimo numero di passi di f sarà O(w^(kf)), dove w è la taglia della stringa.
Quanto ci metterà A a trovare una risposta per il nostro problema?
O(n^(kA)) = O(|f(w)|^(kA)) che, sostituendo f(w) con w, sarà uguale a O(|w|^(kf))^kA.
Visto che tutti sappiamo lavorare con gli esponenti, kf e kA li possiamo moltiplicare. Il risultato sarà O(|w|^(kf*kA)) e kf*kA resta sempre costante, il che rende la trasformazione polinomiale.

Passiamo ora al secondo:
Dobbiamo dimostrare che ogni linguaggio L in NP si riduce in tempo polinomiale a P2. Sappiamo che esiste una riduzione polinomiale di L a P1 che impiega un tempo polinomiale p(n). Quindi una stringa w di L può esere convertita in un'altra stringa in NP-COMPLETE di lunghezza massima p(n).
Supponiamo che esista una riduzione polinomiale di P1 a P2 e che impieghi un tempo polinomiale q(m). La riduzione quindi impiegherà un tempo massimo q(p(n)) per trasformare la stringa w di L. Così la trasformazione impiegherà un tempo massimo p(n)+q(p(n)), che è sempre polinomiale!
Ora, dato che L è un linguaggio a caso in NP, abbiamo dimostrato che l'intera classe NP si riduce a P2, cioè che P2 è NP-COMPLETE!

non ho mai capito la differenza fra NP e NP-COMPLETE....

AAAAA ora ho capito Very Happy

Utente Junior Età : 21 Registrato il : 23/01/08 Messaggi : 341

ragà scusate la mia ignoranza ma perchè bisogna dimostrare i precedenti teoremi... a me pare ovvio che gli enunciati siano giusti... secondo voi sn pazza???
_________________
con arco e frecce catturo anime...

Utente Junior Età : 21 Registrato il : 23/01/08 Messaggi : 341

senza dubbio... effettivamente non avevo pensato che per qualsiasi cosa dire "per me è giusto" e non avere le basi per dimostrarlo annulla il tutto.. Very Happy

_________________
con arco e frecce catturo anime...