Esercizio su RIDUCIBILITÀ POLINOMIALE
Ciao,
a giorni avrò l'orale dell'esame di algoritmi ed ho qualche dubbio su questo esercizio relativo alle riducibilità polinomiali.
L'esercizio dice: Siano A, B e C 3 problemi decisionali, sappiamo che:
1) A è NP-completo
2) B <=p A (B è riducibile polinomialmente ad A)
3) A <=p C (A è riducibile polinomialmente ad C)
Dire se le seguenti affermazioni sono vere o false motivandone le risposte in modo rigoroso (per ora ho fatto solo la prima delle affermazioni richieste...e non sono affatto sicuro di come ho ragionato...quindi chiedo a voi se la strada che stò percorrendo possa essere considerata giusta o se stò facendo casini...)
a) C <=p CIRCUITO HAMILTONIANO Il problema decisionale C è riducibile polinomialmente al problema del Cammino Hamiltoniano?
Io ho ragionato così:
Sò per ipotesti che A <=p C (A è riducibile polinomialmente ad C), questo significa che esiste una funzione che in tempo polinomiale trasforma istanze del problema A in istanze del problema C
Ciò implica che se esistesse un algoritmo polinomiale per C, allora esisterebbe un algoritmo polinomiale per A.
Visto che abbiamo anche l'ipotesi che A è NP-completo, allora posso dire che C è INTRATTABILE
Ho quindi dimostrato che C è intrattabile...ma questo non significa poter dimostrare che C è riducibile polinomialmnete a Cammino Hamiltoniano (quindi che C appartiene ad NP-completo, giusto?) in quanto io sò soltanto che C è intrattabile ma C potrebbe anche essere al di fuori della classe NP (cioè io sò che tutti i problemi in NP sono riducibili polinomialmente a Cammino Hamiltoniano, ma se C fosse fuori NP, quindi fpiù complesso...tipo nella classe esponenziale non sarebbe riducibile polinomialmente a Cammino Hamiltoniano)
Quindi la risposta a questa domanda è FALSO
Ci può stare come ragionamento?
Grazie mille
Andrea
a giorni avrò l'orale dell'esame di algoritmi ed ho qualche dubbio su questo esercizio relativo alle riducibilità polinomiali.
L'esercizio dice: Siano A, B e C 3 problemi decisionali, sappiamo che:
1) A è NP-completo
2) B <=p A (B è riducibile polinomialmente ad A)
3) A <=p C (A è riducibile polinomialmente ad C)
Dire se le seguenti affermazioni sono vere o false motivandone le risposte in modo rigoroso (per ora ho fatto solo la prima delle affermazioni richieste...e non sono affatto sicuro di come ho ragionato...quindi chiedo a voi se la strada che stò percorrendo possa essere considerata giusta o se stò facendo casini...)
a) C <=p CIRCUITO HAMILTONIANO Il problema decisionale C è riducibile polinomialmente al problema del Cammino Hamiltoniano?
Io ho ragionato così:
Sò per ipotesti che A <=p C (A è riducibile polinomialmente ad C), questo significa che esiste una funzione che in tempo polinomiale trasforma istanze del problema A in istanze del problema C
Ciò implica che se esistesse un algoritmo polinomiale per C, allora esisterebbe un algoritmo polinomiale per A.
Visto che abbiamo anche l'ipotesi che A è NP-completo, allora posso dire che C è INTRATTABILE
Ho quindi dimostrato che C è intrattabile...ma questo non significa poter dimostrare che C è riducibile polinomialmnete a Cammino Hamiltoniano (quindi che C appartiene ad NP-completo, giusto?) in quanto io sò soltanto che C è intrattabile ma C potrebbe anche essere al di fuori della classe NP (cioè io sò che tutti i problemi in NP sono riducibili polinomialmente a Cammino Hamiltoniano, ma se C fosse fuori NP, quindi fpiù complesso...tipo nella classe esponenziale non sarebbe riducibile polinomialmente a Cammino Hamiltoniano)
Quindi la risposta a questa domanda è FALSO
Ci può stare come ragionamento?
Grazie mille
Andrea
Risposte
Ciao,
sono andato avanti con le altre domane a cui rispondere vero o falso motivandole dell'esercizio e posto le mie soluzioni nella speranza che qualcuno confermi o smentisca i miei ragionamenti:
I dati sono sempre gli stessi, ho 3 problemi decisionali: A, B e C e sò che:
1) A è NP-completo
2) B <=p A (B è riducibile polinomialmente ad A)
3) A <=p C (A è riducibile polinomialmente ad C)
DOMANDE:
2) Esiste un algoritmo polinomiale K ed un polinomio p tale che se x è una istanza si di B allora esiste y di lunghezza al più p(|x|) per cui K(x,y)=1 (K ritorna VERO); altrimenti (x è istanza no del problema B) per ogni y di lunghezza al più p(|x|) allora K(x,y)=0 (K ritorna FALSO)
Quì ho ragionato così:
Sò che A è NP completo.
Cosa sò di B? So che B <=p A che significa che esiste una funzione che in tempo polinomiale trasforma istanze di B in istanze di A
In questo caso però non è una riduzione polinomiale che mi colloca B nella classe NP-completa (lo sarebbe stato nel caso opposto se avessi avuto A <=p B perchè A è notoriamente NP-completo, se avessi un algoritmo polinomiale per B allora sarebbe polinomiale anche A, quindi B sarebbe NP-completo)
Quindi in pratica quando dice B <=p A è come se mi stesse dicendo che B ha complessità AL PIÙ PARI a quella di A.
Essendo A in NP-completo (me lo dicono i dati dell'esercizio) è un problema che appartiene ad una sottoclasse di NP, quindi è un problema NP.
A questo punto B può essere o NP-completo (se complesso come A) oppure può essere in P
In entrambi i casi è un problema che stà nella classe NP, quindi in entrambi i casi esiste un algoritmo che presi in input:
1)un'istanza x del problema B.
2) Un CERTIFICATO POLINOMIALE y (che per sua natura ha lunghezza al più polinomiale nella dimensione dell'istanza del problema originale, quindi proprio p(|x|) )
torna TRUE se x è ISTANZA SI di B e torna FALSE se x è istanza NO di B
Quindi direi che la risposta è questa domanda è che è VERA la tesi affermata.
--------------------------------------------------------------------------------------------------------------------------------------------------------------
3)B non ammette un algoritmo polinomiale a meno che P = NP
Questa mi sembra palesemente falsa in quando come ho visto nell'esercizio precedente se si ha che B è polinomialmente riducibile ad A (B <=p A) con A che è NP-completo.
Allora si ha che o B è NP-completo oppure B è in P.
Se è in P allora B ammette un algoritmo polinomiale.
-------------------------------------------------------------------------------------------------------------------------------------------------------------
4)B ammette un algoritmo esponenziale
Questa la trovo un po' ambigua come affermazione a cui rispondere vero o falso...
Come si è visto nei due punti precedenti B è al più NP-completo (potrebbe essere addirittura polinomiale), quindi sicuramente posso fare di meglio di un algoritmo esponenziale (perchè la classe esponenziale è una classe che contiene NP)
Ma un programmatore stupido che implementa un algoritmo stupido per risolvere B potrebbe tranquillamente creare un algoritmo esponenziale (basta che crei tipo un algoritmo ricorsivo che ad ogni chiamata generi un numero esponenziali di chiamate a se stesso che non fanno nulla...ed ecco fatto...)
------------------------------------------------------------------------------
Ci stò come ragionamento? E' importante...sono stato ammesso all'orale con un voto non proprio fantastico e per passare l'esame dovrò fare un ottimo orale...
Poi c'è ancora un'altra domanda...forse più complessa...prima di postarla ci penso ancora un po' su
Grazie
Andrea
sono andato avanti con le altre domane a cui rispondere vero o falso motivandole dell'esercizio e posto le mie soluzioni nella speranza che qualcuno confermi o smentisca i miei ragionamenti:
I dati sono sempre gli stessi, ho 3 problemi decisionali: A, B e C e sò che:
1) A è NP-completo
2) B <=p A (B è riducibile polinomialmente ad A)
3) A <=p C (A è riducibile polinomialmente ad C)
DOMANDE:
2) Esiste un algoritmo polinomiale K ed un polinomio p tale che se x è una istanza si di B allora esiste y di lunghezza al più p(|x|) per cui K(x,y)=1 (K ritorna VERO); altrimenti (x è istanza no del problema B) per ogni y di lunghezza al più p(|x|) allora K(x,y)=0 (K ritorna FALSO)
Quì ho ragionato così:
Sò che A è NP completo.
Cosa sò di B? So che B <=p A che significa che esiste una funzione che in tempo polinomiale trasforma istanze di B in istanze di A
In questo caso però non è una riduzione polinomiale che mi colloca B nella classe NP-completa (lo sarebbe stato nel caso opposto se avessi avuto A <=p B perchè A è notoriamente NP-completo, se avessi un algoritmo polinomiale per B allora sarebbe polinomiale anche A, quindi B sarebbe NP-completo)
Quindi in pratica quando dice B <=p A è come se mi stesse dicendo che B ha complessità AL PIÙ PARI a quella di A.
Essendo A in NP-completo (me lo dicono i dati dell'esercizio) è un problema che appartiene ad una sottoclasse di NP, quindi è un problema NP.
A questo punto B può essere o NP-completo (se complesso come A) oppure può essere in P
In entrambi i casi è un problema che stà nella classe NP, quindi in entrambi i casi esiste un algoritmo che presi in input:
1)un'istanza x del problema B.
2) Un CERTIFICATO POLINOMIALE y (che per sua natura ha lunghezza al più polinomiale nella dimensione dell'istanza del problema originale, quindi proprio p(|x|) )
torna TRUE se x è ISTANZA SI di B e torna FALSE se x è istanza NO di B
Quindi direi che la risposta è questa domanda è che è VERA la tesi affermata.
--------------------------------------------------------------------------------------------------------------------------------------------------------------
3)B non ammette un algoritmo polinomiale a meno che P = NP
Questa mi sembra palesemente falsa in quando come ho visto nell'esercizio precedente se si ha che B è polinomialmente riducibile ad A (B <=p A) con A che è NP-completo.
Allora si ha che o B è NP-completo oppure B è in P.
Se è in P allora B ammette un algoritmo polinomiale.
-------------------------------------------------------------------------------------------------------------------------------------------------------------
4)B ammette un algoritmo esponenziale
Questa la trovo un po' ambigua come affermazione a cui rispondere vero o falso...
Come si è visto nei due punti precedenti B è al più NP-completo (potrebbe essere addirittura polinomiale), quindi sicuramente posso fare di meglio di un algoritmo esponenziale (perchè la classe esponenziale è una classe che contiene NP)
Ma un programmatore stupido che implementa un algoritmo stupido per risolvere B potrebbe tranquillamente creare un algoritmo esponenziale (basta che crei tipo un algoritmo ricorsivo che ad ogni chiamata generi un numero esponenziali di chiamate a se stesso che non fanno nulla...ed ecco fatto...)
------------------------------------------------------------------------------
Ci stò come ragionamento? E' importante...sono stato ammesso all'orale con un voto non proprio fantastico e per passare l'esame dovrò fare un ottimo orale...
Poi c'è ancora un'altra domanda...forse più complessa...prima di postarla ci penso ancora un po' su
Grazie
Andrea
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo