Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Algoritmi - Differenza complessità P , NP e NP-C
Forum - Algoritmi - Differenza complessità P , NP e NP-C

Avatar
XBarboX (Member)
Guru


Messaggi: 945
Iscritto: 31/12/2008

Segnala al moderatore
Postato alle 10:38
Sabato, 02/07/2011
Ciao a tutti,
sto studiando la complessità computazionale e purtroppo mi sono bloccato in quanto pur avendo capito  la complessità polinomiale, non capisco che differenze hanno i problemi NP e i NP-C rispetto a quelli polinomiali.
Sareste così gentili da spiegarmelo? Magari anche con qualche stupido esempio :)

Grazie mille!

PM
Avatar
Ultimo (Member)
Guru


Messaggi: 877
Iscritto: 22/05/2010

Up
0
Down
V
Segnala al moderatore
Postato alle 16:44
Sabato, 02/07/2011

I problemi NP_Completi non sono risolvibili con un Algoritmo in un tempo
Polinomiale, almeno fino a questo momento non è stato dimostrato il
contrario.

ma se non è stato dimostrato il contrario non è stato dimostrato neanche che non sono risolvibili in tempo polinominale?! - Alex - 02/07/11 18:01
Non è dimostrato che P = NP - Ultimo - 02/07/11 23:24
a ok=) devo mettermi anch'io a studiare=) - Alex - 03/07/11 10:09


If ok Then GOTO Avanza else GOTO Inizia

PM