Quels sont les problèmes de NP?

Question

J'ai lu l'article sur wikipedia, mais ne pouvait pas comprendre quels sont exactement les problèmes NP. Quelqu'un peut-il me dire à leur sujet et aussi ce qui est la relation d'entre eux avec P problèmes?

Answer 1

problèmes NP sont des problèmes qui donné une solution proposée, vous pouvez vérifier la solution dans un temps polynomial. Par exemple, si vous avez une liste des cours universitaires et la nécessité de créer un calendrier afin que les cours ne seront pas les conflits, ce serait une tâche très difficile (complexité-sage). Cependant, donnée un projet de calendrier, vous pouvez facilement vérifier l'exactitude.

Un autre exemple important du domaine du cryptage: étant donné un nombre qui est le résultat de la multiplication de deux nombres premiers très grands, il est très difficile de trouver les nombres premiers se basant uniquement sur le résultat. Cependant, données deux chiffres, il est très facile de vérifier la solution (les multiplier, comparer).

J'ai choisi intentionnellement des exemples qui sont NP et non en P (à savoir problème qui sont difficiles à trouver la solution pour) afin que vous puissiez comprendre la différence. Tous les problèmes qui sont faciles à résoudre, sont également faciles à vérifier - il suffit de résoudre et de comparer. Autrement dit, P est un sous-ensemble de NP.

Answer 2

Pas vraiment une réponse, parce que le lien de Piccolo est plus utile, mais un chercheur revendications HP ayant fait ses preuves P! = NP, voici le document.

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

Il n'a pas été acceptée, mais je lui souhaite bonne chance pour le 1 M $.