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)
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)
Schreiben Sie uns!
Beitrag schreiben