P≠NP: Atem anhalten!
BLOG: MATHEMATIK IM ALLTAG
Notizen über alles und nichts, von Günter M. Ziegler
Eines der berühmtesten Probleme der Mathematik steht möglicherweise vor der Lösung: am letzten Freitag (6. August) hat der indische Mathematiker Vinay Deolalikar
– 1971 in New Delhi geboren, ein Principal Research Scientist am Forschungslabor von Hewlett Packard, den HP Labs – ein 102-seitiges Manuskript an 21 Kollegen verschickt, in dem er versucht zu beweisen, dass “P nicht gleich NP” ist:
Das P≠NP-Problem ist eines der berühmtesten Probleme der Mathematik. Unter anderem ist es eines der sieben “Millenniumsprobleme”, auf deren Lösung die Clay-Stiftung im Jahr 2000 jeweils eine Million US-Dollar ausgesetzt hat.
Von diesen sieben Problemen ist inzwischen eines gelöst, die Poincaré-Vermutung: Die Lösung hat Grigorij Perelman 2002/2003 vorgelegt, die Ausarbeitung und Überprüfung hat dann aber bis zum Sommer 2006 gedauert – und erst im März diesen Jahres wurde Perelman das Preisgeld zugesprochen – das der aber (nicht unerwartet) abgelehnt hat.
Jetzt also das P≠NP-Problem. Das hat sich aus Überlegungen zur Berechenbarkeitstheorie und Komplexitätstheorie von Turing, Church, Gödel, Edmonds und vielen anderen entwickelt, und wurde Anfang der Siebziger Jahre unabhängig voneinander von Stephen Cook und von Leonid Levin formuliert.
Informell formuliert fragt das Problem,
ob es Berechnungsprobleme gibt, für die eine Lösung schnell überprüft, aber nicht schnell gefunden werden kann.
Formaler geht es um Berechnungen auf einem Modell-Computer, der sogenannten Turing-Maschine: ein theoretisches Modell dafür, was auch heutige Computer mit einem einzelnen Prozessor ohne Parallelität können. Für eine schnelle Berechnung muss die maximale Laufzeit (in Bit-Operationen als Einzelschritte gemessen) durch ein festes Polynom begrenzt sein, das auf die Größe der Eingabedaten (also die Anzahl der Eingabe-Bits) angewendet wird.
Um welches Polynom es sich dabei handelt, ist sekundär. Auch das Berechnungsproblem ist nicht festgelegt: Kandidaten dafür sind die sogenannten NP-vollständigen Probleme, etwa das Problem des Handlungsreisenden (ob es durch einen vorgegebenen Graphen eine Rundreise gibt, die jeden Knoten genau einmal besucht), oder das Rucksackproblem (ob man aus einer vorgegebenen Liste von natürlichen Zahlen eine Teilmenge auswählen kann, die genau die halbe Summe ergibt). Für beide Probleme ist leicht zu sehen, dass eine Lösung (wenn man sie nun kennt, oder rät, oder vorgesagt bekommt) leicht zu überprüfen ist. Aber für das Finden der Lösung kennt man kein polynomiales Verfahren – und wenn Deolalikar recht hat, gibt es eben auch keines.
Soweit meine informelle Skizze. Die offizielle Beschreibung der Clay-Stiftung für das Problem stammt von Stephen Cook … der jetzt auch mitteilt, der Deolalikar-Beweis ein ein “relativ ernsthafter Versuch”:
Aber ich kenne noch keinen Experten, der sagt, er habe den Beweis durchgearbeitet und verstanden. Einen ersten Aufschlag zur öffentlichen Analyse macht Richard Lipton (Georgia Tech) auf seinem Blog: er erläutert sehr grob den Beweisansatz, skizziert aber auch mögliche Bedenken und “Angriffspunkte” gegen den Beweis.
Ich selbst verstehe nicht genug von Komplexitätstheorie, um da mitdiskutieren zu können, verweise aber auf die Vorhersage in meinem neuen Buch “Darf ich Zahlen? Geschichten aus der Mathematik”, wonach das Problem 2012 von einen Inder gelöst wird. Wenn wir Glück haben, liegt die Lösung bis dahin überprüft, anerkannt und gedruckt vor.
Bis dahin halten wir jetzt erstmal den Atem an.
P=NP
… übringens fand sich letzte Woche auch ein Beweisversuch zum Gegenteil “P=NP” im Internet, der aber wohl noch viel skeptischer betrachtet werden muss als der aktuelle Versuch von Herrn Deolalikar: siehe http://arxiv.org/abs/1007.4257
Vorhersage
Aha, und mit welcher Formel wurde die Vorhersage errechnet? 😉
Wieso hat Grigorij Perelman eigentlich seine Prämie abgelehnt? Das war doch wirklich eine herausragende Leistung – gerade im Vergleich, wenn man mitansieht, wofür mitunter die Mio über die Theke gehen – die somit auch einen entsprechenden Wert hat.
Wenn die Prüfung der letzten Lösung ca. 3,5 Jahre benötigt hat, dann wird es bei diesem Lösungskandidaten wohl ähnlich lange dauern. Das ist viel Zeit, um den Atem anzuhalten …
Re: Vorhersage
Für solche Vorhersagen gibt’s keine Formeln, nur Wunschdenken. Ich hab sogar einen Namen vorhergesagt.
Über Perelman gibt’s Halbwissen, Spekulationen. Eine Biographie “Perfect Rigor”, die ich im Reisegepäck habe zum Internationalen Mathematiker-Kongress in Indien. (Ich werde berichten: am Donnerstag werden die Fields-Medaillen vergeben.) Und angeblich gibt es von Perelman einen Absagebrief mit Begründung, den habe ich aber (noch) nicht gesehen, wenn es ihn überhaupt gibt…
Es sieht nicht gut aus….
Der aktuelle Stand der Dinge: Richard Lipton gibt in seinem Blog unter
http://rjlipton.wordpress.com/…-that-p≠np/
eine Übersicht über die Fehler und Bedenken gegen den Beweisversuch, den Deolalikar vorgelegt hat: Der Beweis scheint schon im Ansatz substanzielle Probleme zu haben. Kaum einer wird zur Zeit darauf wetten, dass das (auch korrigiert und poliert) einen vollständigen Beweis gibt. Aber vielleicht findet sich in den Diskussionen darüber eben doch die entscheidende Idee, mit der es dann weiter geht.
Es ist ja bis 2012 auch noch ein wenig Zeit um Ihre Vorhersage doch noch wahr werden zu lassen.
“obsessed with stat. significance”?
Hallo Herr Ziegler,
wie war denn der ICM? Ich wäre sicher nicht der einzige, der neugierig ist, welche Themen und Vorträge Ihnen besonders aufgefallen sind. Worüber wurde in den Pausen gesprochen, welche Gerüchte kursieren in der mathematical community?
Bei der Gelegenheit hier ein link zu einer aktuellen Diskussion zur Verwendung quasimathematischer Rhetorik in den Sozial- und Wirtschaftswiss. War beim ICM Mathematik im gesellsch. Gesamtzusammenhang ein Thema?
Voevodsky: math inconsistent?
Ein faszinierender Vortrag: What if Current Foundations of Mathematics are Inconsistent? in Princeton IAS vor ca. 2 Wochen.
Mathem. als Rockstars:
Hier ein Bericht mit Fotos (G.Z. hatte ca. 1.600 enthusiastische Zuhörer).
Schönes Buch zur RH:
Hier hat ein bedeutender Zahlentheoretiker und Topologe ein schönes Buch zur Riemann’schen Hypothese geschrieben. Von ihm stammt auch die Einsicht, dass Primzahlen Knoten sind. Wieso?
… Fortsetzg.:
…, dass Primzahlen Knoten sind. Wieso?
missing link:
http://mathoverflow.net/questions/49303/mazurs-unpublished-manuscript-on-primes-and-knots/49319#49319
1, 2,.. Politiker beim Zählen:
Führungskräfte und Zahlen, eine Komödie. Ist Seehofer nur ‘halt persönlich etwas aumerös, oder erlebten wir gerade einen ungefilterten Einblick in die trüben mentalen Untiefen von Führungskräften und Eliten?
P-NP Problem
Das sind nur spekulationen ich denke nicht das er es gefunden hat.