Mathematiker will Millenniumsproblem geknackt haben

11. August 2010, 17:32
148 Postings

Inder Vinay Deolalikar veröffentlicht Lösung des P-NP-Problems

Palo Alto - Es waren sieben der größten mathematischen Rätsel, die das Clay Mathematics Institute (CMI) in Cambridge (Massachusetts) im Jahr 2000 als "Millenniums-Probleme" auslobte. Für ihre Lösung wurde ein Preisgeld von je eine Million US-Dollar versprochen - von denen bis jetzt noch kein Cent ausgegeben wurde.

Dabei wurde eines der Probleme gelöst: Der russische Mathematiker Grigori Perelmann veröffentlichte 2002 einen Beweis der Poincaré-Vermutung, der mittlerweile von der Kollegenschaft akzeptiert wurde. Das zurückgezogen lebende Genie lehnte indes das ihm zustehende Preisgeld ab.

Nun behauptet der in den USA lebende Inder Vinay Deolalikar, eine weitere Millenniums-Nuss geknackt zu haben, nämlich das P-NP-Problem, das seit den 1970er-Jahren theoretische Informatiker und Komplexitätstheoretiker beschäftigt. In sehr einfachen Worten geht es dabei darum, ob und wenn ja: mit welchem Aufwand, komplexe Berechnungsprobleme lösbar sind. Anders gesagt: In welcher Beziehung die beiden Komplexitätsklassen P und NP stehen.

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

Deolaikar, der in seinem Brotberuf im kalifornischen Palo Alto für Hewlett-Packard forscht, führt auf knapp 100 seit Montag im Internet abrufbaren Seiten aus, dass P nicht gleich NP ist. Die Überprüfung wird wohl noch einige Zeit dauern. Kollegen trauen Deolaikar, der Spezialist auf diesem Gebiet ist, die Lösung zu. (tasch/DER STANDARD, Printausgabe, 12. 8. 2010)

Share if you care.