Direkt zum Inhalt
P-NP-Problem

Mathematiker präsentiert Lösung für Millennium-Problem

Siebenmal eine Million Dollar Preisgeld lobte die Clay-Stiftung im Jahr 2000 für die Lösung der sieben größten Probleme der modernen Mathematik aus. Schon 2002 löste der Russe Grigoriy Perelman mit dem Beweis der Poincaré-Vermutung das erste dieser Millennium-Probleme, nun behauptet der Inder Vinay Deolalikar, ein weiteres der illustren mathematischen Rätsel geknackt zu haben. Letzten Freitag schickte er ein Manuskript an 21 Mathematiker, in dem er das P-NP-Problem der Komplexitätstheorie gelöst haben will. Es enthält den Versuch eines Beweises, dass P ungleich NP ist.

P und NP sind Problemklassen der Komplexitätstheorie, die sich mit der Frage befasst, ob und mit welchem Aufwand sich ein gegebenes Problem durch einen Algorithmus lösen lässt. Dabei nutzt sie theoretische Modelle von Rechenmaschinen, die Turing-Maschinen, die verschiedene Eigenschaften haben können. Grundsätzlich lassen sich die Probleme beider Klassen mit Hilfe von Algorithmen in einer endlichen Anzahl von Schritten lösen. In welche Klasse ein Problem gehört, hängt davon ab, wie lange eine Turing-Maschine braucht, um das Problem exakt zu lösen.

Die Definition von P und NP basiert auf zwei Arten dieser Turing-Maschinen. Die Komplexitätsklasse P enthält dabei alle Probleme, die sich von einer deterministischen Turing-Maschine, die für alle praktischen Zwecke einem normalen Computer entspricht, in polynomieller Zeit lösen lassen. Das heißt, die Laufzeit des Algorithmus ist proportional der Anzahl der Problem-Elemente hoch einer endlichen Konstante. Für einen Computer ist das einfach, will sagen: nur eine Frage der Zeit.

Die Zeit für die Lösung von NP-Problemen mit einer deterministischen Turing-Maschine dagegen steigt exponentiell an. Um NP-Probleme in polynomieller Zeit zu lösen, bräuchte man eine nichtdeterministische Turing-Maschine. Da es anders als bei der deterministischen Turing-Maschine kein technisches Äquivalent der nichtdeterministischen Turing-Maschine gibt, ist kein Verfahren bekannt, solche Probleme zu lösen.

Das P-NP-Problem ist so bedeutsam, weil die NP-Probleme viele praktisch relevante Fragestellungen einschließen, aber mit heutigen Methoden nur für sehr kleine Systeme exakt lösbar sind, weil die nötige Zeit exponentiell ansteigt. Das bekannteste Beispiel eines solchen Problems ist der Handlungsreisende, der die kürzeste Route sucht, auf der er alle Orte genau einmal besucht und dann zum Ausgangsort zurückkehrt. Auch für die Kryptografie sind die Komplexitätsklassen wichtig, denn die meisten modernen Verschlüsselungsverfahren basieren auf NP-Problemen wie der Primfaktorzerlegung sehr großer Zahlen.

Wenn Deolalikar Recht hat, gibt es grundsätzlich kein Verfahren, derartige NP-Probleme in polynomieller Zeit zu lösen. Noch hat keiner der Experten den 102 Seiten umfassenden Beweis gründlich durcharbeiten können, doch die Fachwelt nimmt die Publikation ernst. Stephen Cook von der University of Toronto, der für die Clay-Stiftung die offizielle Beschreibung des Problems verfasste, nennt Deolalikars Arbeit vorsichtig "einen relativ seriösen Versuch" zur Lösung des Problems, während die Diskussion in den einschlägigen Fachblogs schon voll im Gange ist.

Auch wenn niemand einen groben Fehler findet – den komplexen Beweis auf Herz und Nieren zu prüfen und alle Unklarheiten auszubügeln, kann, wie im Fall der Poincaré-Vermutung, Jahre in Anspruch nehmen. Es wird also noch ein bisschen dauern, bis wir Genaueres wissen.(lf)
32. KW 2010

Dieser Artikel ist enthalten in Spektrum - Die Woche, 32. KW 2010

Lesermeinung

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Leserzuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Leserzuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmer sich leichter auf Ihre Beiträge beziehen können. Vielen Dank!

SciViews