http://www.faz.net/-gqe-90sxa

Norbert Blum : Hat ein Deutscher das Verschlüsselungs-Superproblem gelöst?

Hinter der Verschlüsselung von Daten steckt ein anspruchsvolles mathematisches Problem. Bild: dpa

Es gibt sieben sogenannte Millenium-Probleme, dahinter stecken anspruchsvollste mathematische Rätsel. Nun glaubt ein deutscher Informatiker, ein besonders brisantes gelöst zu haben.

          Es ist ein gewaltiges Problem, gelegentlich gilt es sogar als bedeutendstes Rätsel der gegenwärtigen Informatik – und ein Deutscher hat es nun womöglich gelöst. Die sogenannte P-NP-Vermutung gehört zu jenen insgesamt sieben Millenium-Problemen, auf deren Lösung  das amerikanische Clay Mathematics Institute schon vor 17 Jahren eine Millionenprämie ausgelobt hat. Seither gab es mehr als 100 Beweisversuche, sie alle waren schlussendlich gescheiterten .

          Alexander     Armbruster

          Redakteur in der Wirtschaft.

          Nun hat der an der Universität Bonn lehrende Informatiker Norbert Blum einen Beweis vorgelegt und veröffentlicht, der das Rätsel endgültig lösen soll. Er ist 38 Seiten lang, voll mit anspruchsvoller Mathematik, und trägt den schlichten Titel „A Solution of the P versus NP Problem“ (hier geht es zum Beitrag).

          Wie schnell können Computer ein Problem lösen?

          Seine Veröffentlichung hat schnell die Runde gemacht. Der in Stanford lehrende Professor für Künstliche Intelligenz und KI-Unternehmer Reza Zadeh fragte etwa über den Kurznachrichtendienst Twitter: „Hat irgendjemand bis jetzt einen Fehler in dem P !=NP-Beweis gefunden, den Norbert Blum beansprucht? Norberts vorherige Arbeit ist großartig gewesen.“

          Hinter dem Rätsel steckt, vereinfacht zusammengefasst, die Frage, wie schnell oder effizient Computer ein Problem eines bestimmten Schwierigkeitsgrades (Komplexität) lösen können. Informatiker unterscheiden dabei sogenannte P-Probleme (P steht dabei für den Ausdruck polynomiell) und NP-Probleme, die einfach gesagt schwieriger bis unlösbar sind – und die ein Computer nicht effizient lösen kann. Dabei steht die Spekulation im Raum, dass vielleicht beides letztendlich ineinander übergeht: NP-Probleme schlussendlich also doch in eine Reihe von P-Problemen aufgliedert werden können - und damit effizient lösbar sind.

          Die Frage ist gegenwärtig hochbrisant. Mit ihr steht und fällt im Grunde die Hoffnung auf moderne Verschlüsselung (Kryptographie). Auch derzeit verwendete Verschlüsselungscodes gelten teils schon als NP-Problem, also als nicht effizient lösbar. Wären sie P-Probleme, würde das wohl grundsätzlich bedeuten, dass es nur eine Frage der Zeit ist, bis Computer in der Lage sind, sie alle effizient zu knacken. So schätzt das beispielsweise der amerikanische Physiker Scott Aaronsen ein.

          Blum kommt in seiner Beweisführung nun zu einem Ergebnis, das viele Informatiker erleichtern dürfte – dass P nämlich nicht gleich NP ist, also nicht die grundsätzliche Aushebelung wichtiger Verschlüsselungsverfahren bevorsteht. Dieses Ergebnis hatten Fachleute bislang tendenziell vermutet, alleine der Beweis ist ihnen nicht gelungen.

          Ob das nun der Fall ist, wird sich zeigen. Denn schon vor Blum haben viele Experten so einen Anlauf unternommen. Physiker Aaronson hat einen Anreiz gesetzt, um Blums Beweis genau zu untersuchen. Er hat in seinem Blog angekündigt, 200.000 Dollar darauf zu wetten, dass auch Blums Beweis einen Fehler enthält. Mal sehen.

          Quelle: FAZ.NET

          Weitere Themen

          Jetzt retten wir die Zukunft

          Digitalisierung : Jetzt retten wir die Zukunft

          Die Zeit der Utopien ist vorbei: Zuletzt hat die Digitalisierung der Welt auch ihre Schattenseiten gezeigt. Das ist kein Grund zu verzagen – denn das Ringen um die Zukunft hat gerade erst begonnen.

          Leben mit und vom Elektromüll Video-Seite öffnen

          Giftiger Arbeitsplatz : Leben mit und vom Elektromüll

          Zehntausende Menschen in der Metropole Accra im westafrikanischen Ghana leben von Elektroschrott. Eine Gruppe von Studenten hat eine Firma gegründet, die aus dem Müll futuristische Möbel herstellt. Eine Chance für ehemalige Deponie-Arbeiter.

          Hier können Sie die Rechte an diesem Artikel erwerben.

          Topmeldungen

          Car2Go und DriveNow gehören bald zusammen.

          F.A.Z. exklusiv : Drive Now und Car2Go vor der Fusion

          BMW und Daimler legen ihre Carsharing-Gesellschaften zusammen. Das hilft Kosten zu sparen, hat aber auch strategisches Kalkül.
          Wegen fahrlässiger Verwendung: Sowohl beim Menschen als auch bei Nutztieren verliert das Medikament zusehends an Wirkung.

          Tödliche Keime : Wie der Mensch sich mit Antibiotika selbst entwaffnet

          Antibiotika sollen jährlich Millionen Leben retten. Doch weil Ärzte, Patienten und Landwirte fahrlässig damit umgehen, verlieren sie an Wirkung. Lässt sich der Kampf gegen resistente Erreger noch gewinnen?

          14-Jähriger erstochen : Tödlicher Streit unter Schülern

          Der mutmaßliche Täter von Lünen soll leicht zu provozieren und schon eine Zeit lang nicht mehr im Unterricht gewesen sein. Am Dienstag kam er zum ersten Mal wieder – und stach offenbar unvermittelt einen Mitschüler nieder.

          Newsletter

          Immer auf dem Laufenden Sie haben Post! Abonnieren Sie unsere FAZ.NET-Newsletter und wir liefern die wichtigsten Nachrichten direkt in Ihre Mailbox. Es ist ein Fehler aufgetreten. Bitte versuchen Sie es erneut.
          Vielen Dank für Ihr Interesse an den F.A.Z.-Newslettern. Sie erhalten in wenigen Minuten eine E-Mail, um Ihre Newsletterbestellung zu bestätigen.