Direkt zum Inhalt
Login erforderlich
Dieser Artikel ist Abonnenten mit Zugriffsrechten für diese Ausgabe frei zugänglich.

Komplexitätstheorie: Graphen paaren ist leichter als gedacht

Die Entdeckung eines neuen, hocheffizienten Lösungsverfahrens für ein prominentes Problem der Informatik wirft neues Licht auf die Frage "P = NP?".
Petersen-Graph
Von Spektrum der Wissenschaft übersetzte und redigierte Fassung des Artikels Landmark Algorithm Breaks 30-Year Impasse aus Quanta Magazine, einem inhaltlich unabhängigen Magazin der Simons Foundation, die sich die Verbreitung von Forschungsergebnissen aus Mathematik und den Naturwissenschaften zum Ziel gesetzt hat.

In den undurchdringlichen Dschungel der Komplexitätstheorie ist allem Anschein nach eine bedeutende Schneise geschlagen worden: Der Informatiker László Babai von der University of Chicago hat einen neuen Algorithmus für eines der vertracktesten Rätsel der Informatik gefunden, das Graphen­isomor­phie-Problem. So wie es aussieht, ist das neue Verfahren um Klassen effizienter als sein Vorgänger, der immerhin mehr als 30 Jahre nicht übertroffen wurde.

Babais Ankündigung auf einem Vortrag am 10. November 2015 hat die Szene in helle Aufregung versetzt. "Wenn sein Werk der Nachprüfung standhält, dann ist es eines der großen Resultate des Jahrzehnts – oder sogar mehrerer Jahrzehnte", so Joshua Grochow, ein Informatiker vom Santa Fe Institute. "Ich glaube nicht, dass irgendjemand, außer vielleicht ihm selbst, geglaubt hat, ein solches Resultat würde in den nächsten zehn Jahren herauskommen – oder überhaupt irgendwann."

Babai selbst spricht nicht mit der Presse, solange die Fachkollegen seine Resultate nicht überprüft haben. Diese sind allerdings optimistisch gestimmt, weil er sich mit seinen bisherigen Arbeiten einen erstklassigen Ruf erworben hat

Schreiben Sie uns!

1 Beitrag anzeigen

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, Zuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Zuschriften 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 Teilnehmende sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Zuschriften können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

  • Quelle

Babai, L.: Graph Isomorphism in Quasipolynomial Time. In: arXiv:1512.03547, 2016

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.