Calcolabilità e Complessità : riduzione tra problemi

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

KillerCD ha scritto:

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

Allora la classe NP-COMPLETE comprende tutti quei problemi che sono i più difficili tra quelli in NP, cioè quei problemi di cui è stata dimostrata la NP-hardness (Vedi precedente post di Hiems). La differenza è questa NP-COMPLETE è una sottoclasse di NP. In NP, ci sono tutti i problemi risolvibili con una macchina di Turing non deterministica in tempo polinomiale. Quindi per esempio la ricerca di un elemento in un array è in NP, così come lo è il problema del Vertex Cover. Però il primo non è in NP-complete, il secondo sì. Perchè del secondo è stata dimostrata la NP-hardness appunto, quindi vuol dire che tutti i problemi in NP sono almeno difficili quanto lui. Cosa invece non vera per il problema della ricerca di un elemento in un array. Sono stato spiegato?

AAAAA ora ho capito

KillerCD ha scritto:

AAAAA ora ho capito

ne sei proprio sicuro?

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

ladydarko ha scritto:

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

Se sono giusti è perché sono stati dimostrati -_-

Se per te è ovvio è un buon inizio, ma dire "per me è ovvio" non vuol dire saperlo dimostrare, e la dimostrazione di teoremi può essere relativamente ovvia..

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

Carmine ha scritto:

KillerCD ha scritto:

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

Allora la classe NP-COMPLETE comprende tutti quei problemi che sono i più difficili tra quelli in NP, cioè quei problemi di cui è stata dimostrata la NP-hardness (Vedi precedente post di Hiems). La differenza è questa NP-COMPLETE è una sottoclasse di NP. In NP, ci sono tutti i problemi risolvibili con una macchina di Turing non deterministica in tempo polinomiale. Quindi per esempio la ricerca di un elemento in un array è in NP, così come lo è il problema del Vertex Cover. Però il primo non è in NP-complete, il secondo sì. Perchè del secondo è stata dimostrata la NP-hardness appunto, quindi vuol dire che tutti i problemi in NP sono almeno difficili quanto lui. Cosa invece non vera per il problema della ricerca di un elemento in un array. Sono stato spiegato?

Mi sembra che c'è una leggera differze tra NP-Hard e NP-completo...(mi sembra).
Cioè che un problema NP-Completo è un problema che è NP-Hard (dim. l'hardness) ed è in NP (dim. la membership).
Penso per differenziarli da problemi di classe superiori all'NP (come gli EXP) che sono anche NP-Hard(???detto cavolate???).
...bho..attimo di confusione

garulf ha scritto:

Mi sembra che c'è una leggera differze tra NP-Hard e NP-completo...(mi sembra).
Cioè che un problema NP-Completo è un problema che è NP-Hard (dim. l'hardness) ed è in NP (dim. la membership).
Penso per differenziarli da problemi di classe superiori all'NP (come gli EXP) che sono anche NP-Hard(???detto cavolate???).
...bho..attimo di confusione

Sì ovviamente avevo precisato che il problema era in NP(quindi era stata dimostrata la membership).

La NP-hardness viene dimostrata proprio per distinguere i problemi facili che sono in NP da quelli difficili (che dovrebbero stare sul bordo).

Carmine ha scritto:

garulf ha scritto:

Mi sembra che c'è una leggera differze tra NP-Hard e NP-completo...(mi sembra).
Cioè che un problema NP-Completo è un problema che è NP-Hard (dim. l'hardness) ed è in NP (dim. la membership).
Penso per differenziarli da problemi di classe superiori all'NP (come gli EXP) che sono anche NP-Hard(???detto cavolate???).
...bho..attimo di confusione

Sì ovviamente avevo precisato che il problema era in NP(quindi era stata dimostrata la membership).

La NP-hardness viene dimostrata proprio per distinguere i problemi facili che sono in NP da quelli difficili (che dovrebbero stare sul bordo).

Ecco... no era giusto per capire meglio anchio!...