Newsgroup: it.scienza.informatica
Titolo: Problema NP Completo

Ciao a tutti.
ho cercato su google, ma non ho trovato nulla che possa rispondere in modo 
preciso alla domanda:
"quando un problema si dice NP-completo?"
Tutto quello che ho trovato dà per scontato che il lettore conosca già la 
definizione di NP-completo
Vi sarei grato nel casi in cui vogliate aiutarmi
Grazie anticipatamente
Roberto 

 "quando un problema si dice NP-completo?"
http://mathworld.wolfram.com/NP-CompleteProblem.html
seguendo i link trovi tutte le definizioni dei termini
che eventualmente non conosci.
v.

"Roberto" <gioe...@NOSPAMlibero.it> ha scritto nel messaggio 
news:nAB2e.16832$IN.3...@twister2.libero.it...

P=Polinomiale
NP=Non Polinomiale
Una problema p è NP-completo se può essere ridotto ad un problema NP di 
complessità nota (Non Polinomiale, per l'appunto).
fab 

 complessità nota (Non Polinomiale, per l'appunto).
neanche questa è giusta... un problema è NP-completo se riduce qualunque 
  problema in NP in altri termini qualunque problema in NP può essere 
ridotto (la riduzione deve avere tempo polinomiale) ad un NP-completo
ciao
Mauro

 complessità nota (Non Polinomiale, per l'appunto).
mi dispiace, ma non hai capito assolutamente un acca della teoria
della np-completezza.
Prima di tutto NP non vuole assolutamente  dire Non Polinomiale.
(Nel seguito saro' abbastanza informale, giusto per dare una idea della
cosa).
Ci sono diverse definizioni della classe NP, che e' composta
di problemi decisionali, ovvero problemi per i quali alla fine
la risposta e' un bit, ovvero un valore (Si/No).
Un problema decisionale e' in NP se puo' essere deciso in tempo
polinomiale da una macchina di Turing NON determistica.
Alternativamente possiamo definire la classe NP come quella dei problemi
tali per cui e' possibile fornire un certificato della risposta (Si)
controllabile in tempo polinomiale.
Quindi ad esempio la versione decisionale del problema del commesso 
viaggiatore (TSP) e' in NP, perche' il problema consiste nel decidere,
  date  delle citta' e la lunghezza delle strade che le uniscono, e una 
lunghezza L, se esiste un cammino lungo al massimo L che tocca tutte le
citta' ritornando al punto di partenza.
Il problema e' chiaramente in NP perche' se io dico Si, allora posso
anche fornire un certificato della risposta, ovvero la lista delle
citta' sul ciclo: in effetti il controllo del fatto che il ciclo
e' piu' corto di L si puo' fare banalmente in tempo polinomiale.
E poi un problema non e' NP completo se puo' essere ridotto ad un
problema NP di complessita' nota, ma vale praticamente il viceversa:
in soldoni e senza pretese di rigore,
un problema si dice NP-completo, se tutti i problemi nella classe NP 
possono essere ridotti ad esso, con al piu' un overhead polinomiale.
Cioe' in teoria, sapendo come si risolve quel problema, posso risolvere
tutti i problemi nella classe NP invocando un "solutore" per quel 
problema e aggiungendoci altre operazioni, ma in numero polinomiale.
Senza offesa, ma sarebbe meglio, prima di dare delle risposte, essere
ragionevolmente sicuri di non dire cose grossolanamente errate,
altrimenti si confonde inutilmente l'OP.
ciao,
v.

 NP=Non Polinomiale
Rettifico: NP= Non deterministico Polinomiale
fab

 fab 

 NP=Non Polinomiale
BEEEEEEEEEEP!
NP=Polinomiale Non-deterministico
--
Xelloss 

 da una macchina di Touring Non deterministica
Comunque si chiama macchina di Turing, il Touring Club è un'altra cosa :P
E' uno strafalcione piuttosto diffuso, purtroppo...
Ciao :)