Es gehört seit Jahrzehnten zu den mittelgroßen offenen Problemen der Mathematik: der Komplexitätsstatus des Graphenisomorphie-Problems. Worum geht es?

Einen Graphen kann man sich vorstellen wie eine Straßenkarte, wobei die Straßen im Allgemeinen auch mit Über- und Unterführungen aneinander vorbei geführt werden können. Kreuzen sich zwei oder mehr Straßen in einem Punkt, dann nennt man diesen Punkt einen "Knoten"; die Straßen heißen auf Mathematisch "Kanten". Graphen -- und hier endet der Vergleich mit der Landkarte -- bleiben aber dieselben Graphen, wenn man die Knoten verrutscht, die Kanten in Schlangenlinien zeichnet und alle Knoten und Kanten umbenennt: Es kommt nur darauf an, dass die Gesamtstruktur erhalten bleibt.

Es ist ein Problem mit ziemlich vielen Anwendungen, zwei Graphen daraufhin zu vergleichen, ob sie im Prinzip die gleiche Struktur haben -- oder ob zum Beispiel nach "Rückbenennung" der Straßen und Orte nur eine einzelne Straße zwei völlig andere Orte verbindet. Dieses Problem ist das Graphenisomorphie-Problem.

Seit Jahrzehnten wird daran geforscht, ob man einem Computer beibringen kann, dieses Problem schnell zu lösen. Das mathematische Wort für "schnell" ist hier "in Polynomialzeit". Vielleicht geht das gar nicht. Doch es ist auch nicht klar, wie schwer das Problem ist, im Vergleich zu Problemen, die gemeinhin als schwer bekannt sind -- Paradebeispiel: Das Travelling Salesman Problem. Das nennt man den "offenen Komplexitätsstatus des Graphenisomorphieproblems".

Nun behauptet ein Team von zwei indischen Mathematikern aus Kanpur, Shashank K. Mehta und Pawan Aurora, bei der Lösung dieser zweiten Frage einen Schritt weiter gekommen zu sein. Sie bewiesen, dass man die Isomorphie zweier Graphen dadurch entscheiden kann, dass man für eine Kombination der beiden Graphen eine gewisse Zahl berechnet, die vollständig positive Lovász-Zahl. Diese Zahl zeigt einem an, ob die beiden Ausgangsgraphen isomorph waren oder nicht. Das Interessante: Die Zahl lässt sich näherungsweise in polynomieller Zeit -- also schnell -- berechnen. Ein Hinweis darauf, dass es eines Tages für das Graphenisomorphieproblem vielleicht doch eines Tages einen schnellen Algorithmus gibt?