Cosa sono i problemi NP?

Question

Ho letto l'articolo su Wikipedia ma non sono riuscito a capire cosa siano esattamente i problemi NP.Qualcuno può parlarmene e anche qual è la loro relazione con P Problems?

Answer 1

I problemi NP sono problemi che data una soluzione proposta, è possibile verificare la soluzione in un tempo polinomiale.Ad esempio, se hai un elenco di corsi universitari e devi creare un programma in modo che i corsi non entrino in conflitto, sarebbe un compito davvero difficile (in termini di complessità).Tuttavia, dato un programma proposto, potrai facilmente verificarne la correttezza.

Un altro esempio importante dal campo della crittografia:dato un numero che è il risultato della moltiplicazione di due numeri primi molto grandi, è molto difficile trovare quei numeri primi basandosi solo sul risultato.Tuttavia, dato due numeri, è molto semplice verificare la soluzione (moltiplicarli, confrontarli).

Ho scelto intenzionalmente esempi che sono in NP e non in P (es.problema per il quale è difficile trovare una soluzione) in modo da poter capire la differenza.Tutti i problemi facili da risolvere sono anche facili da verificare: basta risolverli e confrontarli.Cioè P è un sottoinsieme di NP.

Answer 2

Non proprio una risposta, perché il legame di Piccolo è più utile, ma un ricercatore affermazioni HP aver provato P! = NP, qui è la carta.

www.hpl.hp.com/personal/Vinay_Deolalikar/Papers /pnp12pt.pdf

Non è stato ancora accettato, ma gli auguro buona fortuna per il 1M $.