Ressourcen, um mehr über das P vs. NP-Problem zu erfahren

12

Ich wurde kürzlich an das vs. , wie es von Stephen A. Cook am Clay Mathematics Institute erklärt wurde.PNP

Es hat mein Interesse geweckt und ich würde gerne mehr darüber erfahren. Der erste Schritt wäre ein tieferes Verständnis des Problems und des Gebiets im Allgemeinen.

Können Sie Bücher oder andere Ressourcen empfehlen, in denen ich mehr über das Problem erfahren kann?

Jon Cox
quelle
Crossposted von math.stackexchange.com/questions/13742/… , der derzeit keine Antworten hat.
Tsuyoshi Ito

Antworten:

11

Es ist schön zu sehen, dass ein Student mit so viel Enthusiasmus diesem großen Problem nachgeht. Lassen Sie sich von mir aus eigener Erfahrung beraten.

ist ein sehr interessantes Problem. Die Implikationen der Antwort sind immens, insbesondere in dem Fall, dass die beiden Klassen gleich sind. Die Belohnung ist in vielerlei Hinsicht großartig, vom altruistisch-wissenschaftlichen bis zum materialistischen Geldpreis. Das führt dazu, dass viele junge Leute, die auf das Problem stoßen, versuchen, es zu lösen, ohne oder mit nur begrenztem Wissen darüber.PNP

Vielleicht durchlaufen die meisten Theoriestudenten diese Phase. Sie werden eine Idee haben und denken, dass es richtig ist, aber es ist fast sicher, dass Sie sich irren. Manche Menschen kommen nie durch diese Phase und schämen sich, weil sie zu stur sind, um ihre Fehler zuzugeben.

In FOCS 2010 verglich Rahul Santhanam die Frage mit einem mythischen Monster. Es würde viele Opfer und Mut erfordern, um dieses Monster zu besiegen. Immerhin kann es das schwierigste Problem überhaupt sein. Um eine Chance zu haben, müssen Sie viel über dieses Problem und die Komplexität im Allgemeinen lernen. Sie werden nie wissen, was die "Schwäche des Monsters" sein wird.PNP

Mein Rat lautet also: Nehmen Sie sich Zeit, um das Problem zu kennen. Wenn Sie eine Lösung finden, gehen Sie davon aus, dass Sie sich irgendwie geirrt haben, und versuchen Sie, das Problem damit zu finden. So lernst du viel.

Als Referenz würde ich auch Sipsers Buch empfehlen. Nach Abschluss würde ich "Computational Complexity: A modern approach" von Arora und Barak empfehlen, ein komplexeres Buch, das ein gutes Verständnis des Konzepts der Berechnung erfordert.

Chazisop
quelle
4
Vielen Dank für Ihre Worte der Weisheit. Wenn ich ganz ehrlich bin, scheint es für jemanden umso unmöglicher, eine Lösung zu finden, je mehr ich über das Problem erfahre. Auf jeden Fall sehr interessant!
Jon Cox
4
+1 Ich mag es, aber lass mich nicht zustimmen. ist kein Monster, sondern ein sehr schönes Baby, das darauf wartet, dass jemand seinen Schleier hebt, damit die Welt ihre herrliche Schönheit genießen kann. Außerdem ist sie sehr unschuldig und rein und sie versucht nur, die ganze Zeit mit uns zu spielen und uns mit ihren Rätseln PvsNP
Mohammad Al-Turkistany
2
Wenn sie ein Monster wäre, würde ich sofort aufhören, sie zu verfolgen, weil ich Monster hasse :)
Mohammad Al-Turkistany
9

Ich empfehle nachdrücklich Sipsers "Einführung in die Berechnungstheorie", insbesondere weil es mindestens eine der Haupthindernisse für die Lösung von P vs. NP abdeckt, nämlich die Relativierung. Es enthält einen sehr klaren Beweis für das Baker-Gill-Solovay-Ergebnis. Ich bin nicht sicher, ob es irgendetwas über die Razborov-Rudich-Ergebnisse enthält, aber es ist eine fantastische, sehr klare und einfach zu lesende Einführungsressource, um nicht nur über P vs. NP zu lernen, sondern auch für viele andere verwandte Themen in der Komplexitätstheorie. ..das ist wichtig, denn wenn Sie daran interessiert sind, das Problem zu lösen, sollten Sie über Hintergrundinformationen und Ideen für den Einstieg verfügen.

Philip White
quelle
Vielen Dank für den Vorschlag, ich werde ein Exemplar aus der Bibliothek bekommen und es durchsehen müssen :)
Jon Cox
7

PNP

Viel Glück. Das Problem scheint schwer zu sein. :-)

Aaron Sterling
quelle
7
scheint hart zu sein ist eine stark zu unterschätzende Beschreibung der Härte von P vs NP. :)
Hsien-Chih Chang 張顯 張顯
Vielen Dank für den Vorschlag, es gibt eine gute Anzahl an Materialien, die Sie sich ansehen können.
Jon Cox
7

PNP

Mohammad Al-Turkistany
quelle
Vielen Dank für einen hervorragenden Link, ich werde dies meiner erweiterten Leseliste mit hervorragenden Materialien zum Problem hinzufügen :)
Jon Cox
4

Die klassische Referenz für die NP-Vollständigkeit ist das Buch von Garey und Johnson (http://tinyurl.com/2w5yofs). Es ist sowohl lehrreich als auch gründlich.

Persönlich habe ich von Kleinberg Tardos (http://tinyurl.com/37dtyyl) gelernt, weil meine Universität es benutzt hat.

Gautam Kamath
quelle
Ausgezeichnet, ich habe bereits ein Exemplar des Klienberg Tardos-Buches für einen Kurs, den ich mache, und ich werde heute noch Garey und Johnsons Buch aus der Bibliothek holen. Vielen Dank, dass Sie mich darüber informiert haben.
Jon Cox
3

Ich würde auch vorschlagen, eine Probleminstanz zu nehmen und zu versuchen, sie zu lösen. Es ist eine gute Praxis, mit offenen Problemen zu experimentieren. Ich meine, Sie können experimentell Programme schreiben oder bekannte Algorithmen von anderen implementieren und verstehen, wie sie funktionieren, wo sie versagen usw. Außerdem können Sie verschiedene Beweistechniken entdecken. Denken Sie daran, sie werden Sie nicht ins Gefängnis stecken, wenn Sie viel lernen und daran arbeiten und keine Lösung finden. Im Gegenteil, Ihr Kompetenzniveau wird garantiert steigen.

In den meisten Fällen sind diese Probleme im Allgemeinen nur schwer zu lösen als in bestimmten Fällen . Lesen Sie über NFL , um sich ein Bild zu machen.

In meinem Fall war ich bald unter einem Pool von Ideen und verwandten Konzepten begraben worden. Es gibt Programmier- / Codierungsänderungen und theoretische Manöver. Wenn Sie beispielsweise eine Probleminstanz mithilfe von Genetic Algorithm-Konzepten lösen möchten, werden Sie bald feststellen, dass nur GA eine riesige Welt zu entdecken ist! Ich habe kürzlich etwas über Linkage Learning in GA / EA erfahren . Ich weiß aber nicht viel darüber.

Wenn Sie versuchen, die Dinge zu verschlüsseln, werden Sie feststellen, dass einige Programmiersprachen / Tools besser / einfacher sind als andere. Ich habe mich in die Diskussion verirrt, warum Alex Stepenov OOP für mathematisch falsch hält und was der Vorteil der funktionalen Programmierung ist. Ich habe die Spur nicht, aber ich erinnere mich noch genau, dass ich am Anfang ein NP-Complete / Hard-Problem studiert habe.

Ich begrüße Sie, denn die Reise ist abenteuerlich!


quelle
3

P, NP und NP-Vollständigkeit: Die Grundlagen der Komplexitätstheorie von Oded Goldreich wären ein weiteres gutes Einführungsbuch.

Nach einführenden Inhalten möchte ich auch The P = NP Question und Gödels Lost Letter von Richard J. Lipton empfehlen .

Abuzer Yakaryilmaz
quelle
Sayin Abuzer yakaryilmaz ... Das zweite von Ihnen vorgeschlagene Buch ist kostenlos auf seiner Website verfügbar.
Tayfun Pay
geekster-- denk, du irrst dich. Er hat einen Blog mit dem gleichen Namen, aber er hat nicht das Buch
vzn
2

Ich empfehle den ausgezeichneten Übersichtsartikel von Lance Fortnow, "Der Status des P versus NP-Problems" , in dem einige neue Herangehensweisen an das Problem diskutiert werden.

Marko Amnell
quelle
Vielen Dank, dass Sie mich über diesen Artikel informiert haben. Es sieht auf jeden Fall so aus, als wäre er eine Lektüre wert.
Jon Cox