Problemi P e NP
Ho sentito recentemente parlare di questi Problemi del millennio e soprattutto di questo problema legato all informatica e ai problemi P e Np.
La cosa che però non riesco bene a capire è come si risolve questa cosa..ovvero..
un modo per risolverla sarebbe rendere un problema di tipo NP-completo di tipo P, ma facciamo un esempio pratico:
ho saputo che il gioco del Mastermind è catalogato come problema np-completo, in quanto per risolverlo ci vorrebbero tutti i tentativi, il che vuol dire che all aumentare dei colori del gioco il numero di mosse aumenta di $ (n)^(n) $ .
Quindi se si trovasse un metodo per risolvere il gioco nel quale siano sufficienti meno tentativi, o meglio, all aumentare del nuemro di colori il numero di mosse aumenti più lentamente (linearmente) il quesito sarebbe risolto?
è così che funziona?
La cosa che però non riesco bene a capire è come si risolve questa cosa..ovvero..
un modo per risolverla sarebbe rendere un problema di tipo NP-completo di tipo P, ma facciamo un esempio pratico:
ho saputo che il gioco del Mastermind è catalogato come problema np-completo, in quanto per risolverlo ci vorrebbero tutti i tentativi, il che vuol dire che all aumentare dei colori del gioco il numero di mosse aumenta di $ (n)^(n) $ .
Quindi se si trovasse un metodo per risolvere il gioco nel quale siano sufficienti meno tentativi, o meglio, all aumentare del nuemro di colori il numero di mosse aumenti più lentamente (linearmente) il quesito sarebbe risolto?
è così che funziona?
Risposte
Magari il quesito va in "Informatica"...
Più o meno. Formalizzando: se trovi e dimostri esista un algoritmo che risolve il MM in tempo al più polinomiale, ovvero con un numero di operazioni che può essere espresso, rispetto alla complessità $n$ del problema, con un polinomio in funzione di $n$.
Quindi se si trovasse un metodo per risolvere il gioco nel quale siano sufficienti meno tentativi, o meglio, all aumentare del nuemro di colori il numero di mosse aumenti più lentamente (linearmente) il quesito sarebbe risolto?
Più o meno. Formalizzando: se trovi e dimostri esista un algoritmo che risolve il MM in tempo al più polinomiale, ovvero con un numero di operazioni che può essere espresso, rispetto alla complessità $n$ del problema, con un polinomio in funzione di $n$.
e non solo, dopo aver trovato la soluzione per un problema NP in tempo pollinomiale avresti risolto il problema P contro NP con soluzionepositiva poichè la soluzione di ogni problema NP può essere ricondotta alla soluzione di un qualunque altro problema NP.A tal proposito ti consiglio le dispense dove io ho studiato algoritmi,le ultime pagine trattano brevemente in modo piuttosto chiaro il problema di P contro NP
http://info.iet.unipi.it/~fondii/Algori ... ritmi.html
http://info.iet.unipi.it/~fondii/Algori ... ritmi.html
ok, rendo la domanda più semplice: questo n di cui parli cos è?
il numero di colori del mastermind?
cioè se io ho trovato un sistema che risolve un mastermind a N COLORI e 4 BUCHI in AL MASSIMO
N+24 tentativi, ho risolto il problema?
il numero di colori del mastermind?
cioè se io ho trovato un sistema che risolve un mastermind a N COLORI e 4 BUCHI in AL MASSIMO
N+24 tentativi, ho risolto il problema?
"Hop Frog":
ok, rendo la domanda più semplice: questo n di cui parli cos è?
il numero di colori del mastermind?
cioè se io ho trovato un sistema che risolve un mastermind a N COLORI e 4 BUCHI in AL MASSIMO
N+24 tentativi, ho risolto il problema?
Da quello che sembra da questo:
http://arxiv.org/PS_cache/cs/pdf/0512/0512049v1.pdf
l'N relativo al quale è NP non è il numero dei colori ma il numero dei buchi...
P.S: da una occhiata in giro comunque ho l'impressione che il tuo algoritmo per 4 buchi sia piuttosto inefficiente e che il si possa riuscire in un numero di mosse molto più vicino al numero dei colori...
Ok ma quindi la funzione che dev essere di tipo polinomiale ha come "incognita" la lunghezza del codice?
e i colori non importa quanti siano?
e i colori non importa quanti siano?
"Lunghezza del codice"..? "Non importa quanti"..? Io non capisco cosa tu intenda dire.
"Hop Frog":
Ok ma quindi la funzione che dev essere di tipo polinomiale ha come "incognita" la lunghezza del codice?
e i colori non importa quanti siano?
Beh, leggiti la dimostrazione che ho segnalato. Io non mi sono mai occupato del problema ma almeno le prime pagine non mi sembrava contenessero parti di difficile comprensione.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo