Newsgroup: it.scienza.informatica
Titolo: NP e NP-completo

Dimenticavo,
un problema NP-completo è un problema che potrebbe essere trasformato in un
problema P?
Quindi, è giusto dire che i problemi P, NP-completi, ed NP sono nell'ordine
i problemi per cui è sempre più difficile sapere di quanto tempo avranno
bisogno per essere risolti?
Grazie
--
Noixe
--
"Dello scorso Sanremo cosa ne pensi?"
"Penso che quella roba, così strutturata, sia per malati terminali e donne
depresse."
RexAnthony, il signore della Techno-Hardcore

 bisogno per essere risolti?
Qui c'è una grande confusione, andiamo con ordine.
Un problema appartiene alla classe P se esiste un algoritmo polinomiale
che risolva ogni sua istanza (ossia il tempo di esecuzione dell'algoritmo
su un'istanza di lunghezza n è limitato superiormente da una funzione
O(n^k), con k costante opportuna).
Per definire i problemi NP occorrerebbe parlare di macchine
non-deterministiche; probabilmente però il modo più semplice per farteli
capire è il seguente:
un problema appartiene alla classe NP se esiste un algoritmo che, data una
possibile soluzione del problema, verifica in tempo polinomiale se la
soluzione è corretta.
Ovviamente tutti i problemi P sono anche NP. Per certi problemi NP si è
scoperto soltanto recentemente un algoritmo di risoluzione polinomiale (ad
es. il test di primalità).
Infine un problema è NP-completo se ogni istanza di ogni problema NP può
essere convertita in un'opportuna istanza del problema NP completo in
tempo polinomiale, in modo tale che risolvendo il problema NP-completo
viene risolto anche ogni problema NP. In altre parole, se trovassi una
soluzione polinomiale per un problema NP-completo, ne seguirebbe che tutti
i problemi NP hanno soluzioni polinomiali, ossia P = NP.
Tutte e 3 le classi sono risolvibili in tempo finito anche se per le
ultime due allo stato attuale si hanno solo algoritmi approssimati o
esponenziali.
Saluti.
-- 
\/               
wirix...@libero.it
          ICQ UIN: 3233084
/\ e l l o s s   (per rispondermi in privato, elimina il DEMONE)

 un problema P?
un problema decisionale e' in P se e' risolvibile in tempo polinomiale da
una macchina di Touring deterministica (cioe' un calcolatore come quelli
cono cui abbiamo a che fare ogni giorno)
un problema in NP e' un problema decisionale che puo' essere risolto in
tempo polinomiale da una macchina di Touring non deterministica (immaginala
come un multiprocessore con infiniti processori)
ogni problema in P e' anche in NP
un problema NP-completo e' un problema in NP che riduce qualunque problema
in NP in tempo polinomiale cioe' qualunque problema in NP puo' essere
trasformato in un tempo polinomiale in quel problema NP-completo
gli NP-completi sono una classe di equivalenza rispetto all'operazione di
riduzione all'interno degli NP
se non e' chiaro prova a guardare qui:
http://en2.wikipedia.org/wiki/Computational_complexity_theory
e qui:
http://en2.wikipedia.org/wiki/Complexity_classes_P_and_NP
Mauro
-- 
Computer science is no more about computers than astronomy is about
telescopes
        - Edsger Dijkstra

 riduzione all'interno degli NP
Quindi basta risolvere un NP-completo qualsiasi affinchè si abbia NP = P ?
Ma allora gli NP-completi erano degli NP per i quali è stato scoperto che
appartengono alla classe NP-completi? Per caso si stanno cercando altri
problemi NP-completi magari più semplici da risolvere in modo da poter
dimostrare che NP = P?
Grazie
--
Noixe

 cono cui abbiamo a che fare ogni giorno)
Volevo dire che un polinomio potrebbe contenere anche un esponenziale, ma se
non sbaglio quando si fa l'analisi della complessità computazione di un
algoritmo il polinomio che ne viene fuori, avrà un monomio del tipo n^k per
qualche k quindi non è esponenziale ma è una potenza :)
Ciao
--
Noixe

 n^k per qualche k quindi non è esponenziale ma è una potenza :)
se all'esponente c'e' una costante (per quanto grande) e' un polinomio
se all'esponente c'e' una variabile cioe' nell'esponente si trova la
dimensione dell'input del problema allora e' un esponenziale
le loro curve sono molto diverse exp >> n^k


 semplici da risolvere in modo da poter dimostrare che NP = P?
qundo ci si trova con un problema NP lo si cerca di mettere in P o in NP
ci sono molti problemi in NP di cui non si sa dire in che classe stanno
se si dimostrasse che un problema in NP non puo' essere in P allora P!=NP
se si trovasse un soluzione in P ad un problema NP_completo allora P=NP


Discutendo con i miei amici di NP-Completezza č venuto fuori un problema
interessante..
Sia Q il seguente problema decisionale :
    "Esiste un problema NP Completo risolvibile con un algoritmo
polinomiale?"
Come č noto risolvere questo equivarrebbe a dimostrare P=NP (si suppone che
P!=NP)...
la domanda č:
Q appartiene a P??appartiene a NP?appartiene a NPC?
enjoy..bandian

 Q appartiene a P??appartiene a NP?appartiene a NPC?
Ne all'uno ne all'altro: il problema non ha dipende da un parametro n.
Ciao,
unit

 Ne all'uno ne all'altro: il problema non ha dipende da un parametro n.
Direi che non dipende proprio da nessun parametro.
Per cui per le caratteristiche degli algoritmi e delle MdT direi che se
esistesse un algoritmo per risolvere il problema dato, ci impiegherebbe un
tempo costante. O(1) è anche O(n^k) per qualsiasi k, per cui in questo
caso la risposta sarebbe: Q appartiene a P.
Ma sorge il dubbio (fondato) che la funzione che calcola Q non sia
calcolabile.


 calcolabile.
Pardon, ho detto una stupidaggine. Le funzioni zeroarie che restituiscono
valori in {0, 1} sono solamente due: le costanti true e false. Esse sono
senza dubbio calcolabili, in tempo costante.
Per cui dire se esistono problemi NP-completi risolubili in tempo
polinomiale č un problema in P: solo che non sappiamo esattamente qual č la
funzione che lo risolve!
(Se ho detto qualche stupidaggine, spero che qualcuno mi corregga).


Dunque, se il problema iniziale puo' essere calcolato allora il tempo è
costante ed è,  in effetti,  banalmente in P anche se la cosa è poco
interessante (questo mi salva =)). Pero' il problema potrebbe (credo, nn
sono un esperto) essere indecidibile, ed in tal caso immagino che
l'appartenenza a P sia solo una questione di definizione, ma in ogni caso il
succo rimane: il tutto è poco interessante.
Ciao,
unit

Questa č la mia firma :(


 ha scritto nel messaggio
news:mRiLb.28397$Jw2....@tornado.fastwebnet.it...
