Allgemein, Informatik, Mathematik

Gibt es einen Beweis für das P vs NP – Problem?

Gestern Vormittag erreichte mich eine spannende Nachricht: Beim arXiv wurde am vergangenen Freitag (11. August) ein Paper von Norbert Blum hochgeladen. In diesem Paper wird nicht weniger behauptet, als dass er die Frage, ob und NP-Probleme eigentlich zur gleichen Klasse gehören, gelöst habe. Das wäre ein echter Hammer und ihm wäre ein Eintrag in die mathematischen und informatischen Geschichtsbücher sicher!


Norbert Blum ist Professor für Mathematik am Institut der Informatik der Universität in Bonn. Als Forschungsgebiete stehen auf seiner Homepage vor allem diskrete Mathematik, kombinatorische Optimierung und auch Approximationsalgorithmen für NP-harte Probleme. Die ersten Reaktionen auf sein Paper fallen zwar gemischt aus, es gibt viele skeptische Stimmen, aber gleichzeitig auch durchaus Anerkennung. Ob der Beweis lückenlos ist, wird noch zu überprüfen sein, inzwischen dürften einige Fachleute daran sitzen. Ich selbst habe das Paper nur kurz durchgeblättert, aber das Thema gehört leider überhaupt nicht zu meinem Spezialgebiet. Aber ich bin sehr gespannt, wie sich diese Geschichte entwickeln wird!

Fast hätte ich es vergessen: Ihr möchtet sicher gern wissen, wie denn nun die Antwort von Norbert Blum ist… Sind P und NP-Probleme eigentlich eine Klasse von Problemen? Nein, das sind sie laut ihm nicht! Das wäre eine extrem erleichternde Antwort für die Sicherheit von Kryptographie.

Wer noch einmal gern wissen möchte, was es mit dem P vs NP – Problem auf sich hat, worum es eigentlich geht und warum es eines der Millenniums-Probleme ist, dem empfehle ich meinen Artikel über genau dieses Thema: Klick!
Und wer selbst gern mal einen Blick auf diesen (angeblichen) Beweis werfen möchte, kann das hier tun: Klick!

Noch ein paar weitere Einschätzungen gibt es beispielsweise bei Spektrum der Wissenschaft: Klick!

~~~~~~~~~~~~~~~~~~~

UPDATE: Am 30. August hat Norbert Blum seinen Beweis zurückgezogen und ihn selbst für nicht vollständig erklärt. Wir werden also leider noch weiter auf einen endgültigen Beweis warten müssen!

~~~~~~~~~~~~~~~~~~~

Bildquelle: Homepage von Prof. N. Blum von der Universität Bonn

Werbeanzeigen

Ich freue mich auf deinen Kommentar!

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden /  Ändern )

Google Foto

Du kommentierst mit Deinem Google-Konto. Abmelden /  Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden /  Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden /  Ändern )

Verbinde mit %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.