Direkt zum Inhalt
Login erforderlich
Dieser Artikel ist Abonnenten von Spektrum der Wissenschaft 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

April 2016

Dieser Artikel ist enthalten in Spektrum der Wissenschaft April 2016

Lesermeinung

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, Leserzuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Leserzuschriften 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 Teilnehmer sich leichter auf Ihre Beiträge beziehen können. Vielen Dank!

  • Quelle

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