[OT] Definizione di classe NP

[GabbOne]

Ragazzi mi potete dare una mano con questa definizione , soprattutto quando si parla di certificato e di verificabilità


CLASSE NP:
classe dei problemi verificabili polinomialmente
mediante l’applicazione di un certificato
(Dato un problema A ed un certificato c verifichiamo in tempo
polinomiale se c rappresenta una soluzione di A)



Ciao

[kerbero]

Per problemi NP si intende l'insieme di quei problemi per cui non è ancora stato trovato un algoritmo in grado di risolverli in tempo polinomiale (si crede fortemente che non sarà mai possibilie trovarne). Tuttavia se viene data la soluzione del problema NP questa si può verificare in tempo polinomiale.
Un esempio di problema NP è il Sudoku: per trovare la soluzione gli algoritmi attualmente conosciuti ci impiegano tempo esponenziale. Tuttavia se viene già fornita la soluzione (l'insieme delle cifre da immettere nelle rispettive caselle) questa si può verificare in tempo polinomiale, semplicemente riempiendo la tabella e verificando che non dia errori.

Spero di esserti stato d'aiuto....

[GabbOne]

Grazie kerbero mi sei sei stato di aiuto perche anche io pensavo ad una cosa del genere ma non nè ero totalmente convinto . Questo perchè non riuscivo a capire cosa centrava la verificabilità di un problema in un contesto in cui si cerca di capire in che classe si trovano determinati problemi dove per problema si intende una funzione che va dall'insieme delle istanze a quello delle soluzioni(quindi si parla di soluzioni e non di verificabilità