Ressources pour en savoir plus sur le problème P vs. NP

12

On m'a récemment rappelé le problème vs comme expliqué par Stephen A. Cook sur Clay Mathematics Institute.N PPNP

Cela a piqué mon intérêt et j'aimerais en savoir plus. La première étape serait d'acquérir une compréhension plus approfondie du problème et une compréhension du domaine en général.

Pouvez-vous recommander des livres ou d'autres ressources pour en savoir plus sur le problème?

Jon Cox
la source
Crossposted from math.stackexchange.com/questions/13742/… , qui n'a actuellement aucune réponse.
Tsuyoshi Ito du

Réponses:

11

C'est bon de voir un collègue de premier cycle poursuivre ce grand problème avec un tel enthousiasme. Permettez-moi de vous offrir un conseil de mes propres expériences.

PNP est un problème très intéressant. Les implications de la réponse sont immenses, surtout dans le cas où les deux classes sont égales. La récompense est grande à plusieurs niveaux, du scientifique altruiste au prix de l'argent matérialiste. Cela amène de nombreux jeunes qui rencontrent le problème à essayer de le résoudre, sans ou avec peu de connaissances à ce sujet.

Peut-être que la plupart des étudiants théoriques passent par cette phase. Vous aurez une idée et penserez que c'est juste, mais il est presque certain que vous vous trompez. Certaines personnes ne franchissent jamais cette phase et se gênent en étant trop têtues pour admettre leurs erreurs.

Dans FOCS 2010, Rahul Santhanam a comparé la question à un monstre mythique. Il faudrait beaucoup de sacrifices et de courage pour essayer de vaincre ce monstre. Après tout, c'est peut-être le problème le plus difficile de tous les temps. Pour avoir une chance de combattre, vous devrez étudier beaucoup ce problème et la complexité en général. Vous ne saurez jamais quelle sera la "faiblesse du monstre".PNP

Donc, mon conseil est le suivant: prenez votre temps pour connaître le problème. Chaque fois que vous trouvez une solution, supposez que vous vous trompez et essayez de trouver le problème. De cette façon, vous apprendrez beaucoup.

En ce qui concerne les références, je recommanderais également le livre de Sipser. Après l'avoir terminé, je recommanderais "Computational Complexity: A modern approach" par Arora et Barak, un livre plus axé sur la complexité, qui nécessite une bonne compréhension du concept de calcul.

chazisop
la source
4
Merci pour vos paroles de sagesse. Si je suis tout à fait honnête, plus j'en apprends sur le problème, plus il semble impossible pour quelqu'un de trouver une solution. Certainement très intéressant cependant!
Jon Cox
4
+1 J'aime, mais je ne suis pas d'accord. n'est pas un monstre mais une très belle fille qui attend que quelqu'un lève son voile pour que le monde puisse profiter de sa beauté glorieuse. De plus, elle est très innocente et pure et elle essaie juste de jouer avec nous et de nous taquiner avec ses puzzles tout le temps ...PvsNP
Mohammad Al-Turkistany
2
De plus, si elle était un monstre, j'arrêterais immédiatement de la poursuivre parce que je déteste les monstres :)
Mohammad Al-Turkistany
9

Je suggère fortement «l'introduction à la théorie du calcul» de Sipser, en particulier parce qu'elle couvre au moins l'un des principaux obstacles à la résolution de P vs. NP, à savoir la relativisation. Il contient une preuve très claire du résultat Baker-Gill-Solovay. Je ne suis pas sûr qu'il contienne quoi que ce soit sur les résultats de Razborov-Rudich, mais c'est une ressource d'introduction fantastique, très claire et facile à lire pour apprendre non seulement sur P vs NP mais pour de nombreux autres sujets connexes en théorie de la complexité. ..qui est important parce que si votre intérêt est d'essayer de résoudre le problème, vous voudrez avoir une certaine expérience dans le domaine et des idées pour commencer.

Philip White
la source
Merci pour la suggestion, j'obtiendrai une copie de la bibliothèque et j'aurai jeté un coup d'œil :)
Jon Cox
7

La meilleure collection de liens en un seul endroit est probablement la section Lectures complémentaires du wiki qui a été constituée pour aider à évaluer la preuve alléguée de Deolalikar que .PNP

Bonne chance. Le problème semble être difficile. :-)

Aaron Sterling
la source
7
semble être difficile est une description très surestimée de la dureté de P vs NP. :)
Hsien-Chih Chang 張顯 之
Merci pour la suggestion, il y a un bon nombre de documents à vérifier.
Jon Cox
4

La référence classique pour l'exhaustivité de NP est le livre de Garey et Johnson (http://tinyurl.com/2w5yofs). C'est à la fois instructif et approfondi.

Personnellement, j'ai appris de Kleinberg Tardos (http://tinyurl.com/37dtyyl), car mon université l'a utilisé.

Gautam Kamath
la source
Excellent, j'ai déjà une copie du livre Klienberg Tardos pour un cours que je fais, et je vais obtenir le livre de Garey et Johnson à la bibliothèque plus tard dans la journée. Merci de m'avoir prévenu.
Jon Cox
3

Je suggérerais également de prendre un exemple de problème et d'essayer de le résoudre. C'est une bonne pratique d'expérimenter avec des problèmes ouverts. Par expérience, je veux dire, vous pouvez écrire des programmes ou implémenter des algorithmes connus par d'autres et comprendre comment ils fonctionnent, où ils échouent, etc. De plus, vous pouvez découvrir plusieurs techniques de preuve. N'oubliez pas qu'ils ne vous mettront pas en prison si vous étudiez et travaillez beaucoup sur ce sujet et que vous ne trouvez aucune solution. Au contraire, votre niveau de compétence est garanti d'augmenter.

Dans la plupart des cas, ces problèmes sont en général plus difficiles à résoudre que leurs cas spécifiques . Lisez à propos de la NFL pour vous faire une idée.

Dans mon cas, j'avais été bientôt enterré sous un pool d'idées et de concepts connexes. Il y a des ajustements de programmation / codage et des manœuvres théoriques. Comme par exemple, si vous voulez résoudre une instance de problème en utilisant les concepts de l'algorithme génétique, vous découvrirez bientôt que GA seul est un vaste monde à découvrir! J'ai récemment découvert Linkage Learning dans GA / EA. Je n'en sais pas grand-chose cependant.

De plus, lorsque vous essayez de coder les choses, vous constaterez que certains langages / outils de programmation sont meilleurs / plus faciles que d'autres. J'étais perdu dans la discussion sur les raisons pour lesquelles Alex Stepenov pense que la POO est mathématiquement incorrecte et quel est l'avantage de la programmation fonctionnelle. Je n'ai pas de piste mais je me souviens clairement, au début, j'étudiais un problème NP-Complete / Hard.

Je vous souhaite la bienvenue, car le voyage est certes aventureux!


la source
3

P, NP et NP-Completeness: The Basics of Complexity Theory par Oded Goldreich serait un autre bon livre d'introduction.

Après le contenu introductif, je voudrais également recommander The P = NP Question et Gödel's Lost Letter de Richard J. Lipton.

Abuzer Yakaryilmaz
la source
Sayin Abuzer yakaryilmaz ... Le deuxième livre que vous avez proposé est disponible gratuitement sur son site Internet.
Tayfun Payez
geekster-- pensez que vous vous trompez. il a un blog du même nom mais il n'a pas le livre
vzn
2

Je recommande l'excellent article de revue de Lance Fortnow, "The Status of the P versus NP Problem" , qui traite de nouvelles approches du problème.

Marko Amnell
la source
Merci de m'avoir informé de cet article, il semble vraiment qu'il vaut la peine d'être lu.
Jon Cox