P≠NP: Atem anhalten!

BLOG: MATHEMATIK IM ALLTAG

Notizen über alles und nichts, von Günter M. Ziegler
MATHEMATIK IM ALLTAG
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

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:
 
Email Deo
 
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.
 
Clay screenshot
 
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”: 
 
Email Stephen Cook
 
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.

Veröffentlicht von

Professor für Mathematik an der Freien Universität Berlin, Leiter des “Medienbüros” der Deutschen Mathematiker-Vereinigung, Aktivist, Kommunikator, Sekttrinker, Gelegenheitsblogger, Kolumnist und Buch-Autor: "Darf ich Zahlen?" und "Mathematik - Das ist doch keine Kunst!".

13 Kommentare

  1. Vorhersage

    … 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.

    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 …

  2. 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…

  3. 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.

  4. “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?

  5. 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?

  6. 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?

Schreibe einen Kommentar