Stellen Sie sich vor, Ihnen kommt die verantwortungsvolle Aufgabe zu, ein neues U-Bahn-Netz für Ihre Stadt zu bauen. Die Punkte, die das Schienennetz miteinander verbinden soll, sind natürlicherweise vorgegeben: Wichtige Orte der Innenstadt sollen eine Haltestelle erhalten, ebenso wie Bahnhöfe, Flughäfen, Universitäten oder kulturelle Einrichtungen wie Museen und Parks. Gleichzeitig verfügen Sie über ein begrenztes Budget. Das System sollte also möglichst effizient sein: Jeder Ort muss erreichbar sein, wobei die gesamte Tunnellänge aber möglichst klein ausfallen sollte. Wie lösen Sie diese Aufgabe?

Wie sich herausstellt, sind solche so genannten Steinerbaum-Probleme gar nicht so einfach zu lösen. Erstmals tauchte die Frage nach optimalen Netzwerken im frühen 19. Jahrhundert auf. Zwar sind die Aufgaben nach dem Schweizer Mathematiker Jakob Steiner benannt, der auch tatsächlich daran arbeitete. Doch untersucht hatte sie bereits 1811 der französische Gelehrte Joseph Diez Gergonne. Sie müssen aber nicht verzweifeln, wenn Sie nicht auf Anhieb eine gute Lösungsstrategie finden. Denn nach etwas mehr als 150 Jahren wurde klar, dass Steinerbaum-Probleme zu den komplexesten Aufgaben der Mathematik gehören. Es stellt sich jedoch heraus, dass es Lebewesen gibt, die sich mit dieser Art der optimalen Netzwerkplanung sehr leicht tun: Schleimpilze.

Der begabte Stadtplaner-Schleimpilz, Physarum polycephalum, ist ein Einzeller – allerdings kann diese eine Zelle mehrere Quadratmeter groß werden. Die Organismen besitzen weder ein komplexes Nervensystem noch ein Gehirn. Und trotzdem sind sie in der Lage, die erstaunlichsten Aufgaben zu meistern, mit denen sich teilweise manche Säugetiere oder sogar Menschen schwertun: Sie finden die kürzesten Routen innerhalb von Labyrinthen, scheinen eine Art Kurzzeitgedächtnis zu besitzen und können die Verbindungen des Schienennetzes in der Metropolregion von Tokio nachbauen.

Um den Schleimpilz bei der Planung eines optimalen Schienennetzes zu beobachten, muss man ihn mit Futter locken. Seine Leibspeise: Haferflocken. Im Jahr 2010 haben Forscherinnen und Forscher der Universität Hokkaido in Japan in einem Experiment das Getreide so verteilt, dass es Tokio und 36 umliegende Städte der Metropolregion darstellte. Dann platzierten sie Physarum polycephalum auf der Tokio-Haferflocke. Pro Stunde wächst der Schleimpilz um etwa einen Zentimeter an. Daher filmten die Fachleute den Organismus 26 Stunden lang. Der Einzeller fing an, sich in alle Richtungen flach auszubreiten, um nach Haferflocken zu suchen. Um auf Dauer Ressourcen zu sparen und die endlichen Futtermittel möglichst effizient zu verwerten, zog sich der Schleimpilz dann wieder zusammen. Damit umspannte er am Ende die verschiedenen Futterquellen nur noch mit einem Netzwerk aus hauchdünnen Fäden. Wie die Forscher und Forscherinnen erkannten, ähnelte das sich ergebende Muster dem Schienennetz der Metropolregion von Tokio. Laut den Fachleuten hat das vom Schleimpilz entwickelte Netzwerk eine »ähnliche Effizienz, Fehlertoleranz und Netzwerklänge«, was – wie man zugeben muss – für einen Einzeller eine durchaus beachtliche Leistung ist.

Denn die Planung eines Schienennetzes kann in manchen Fällen selbst für Computer eine schwierige Aufgabe darstellen. Angenommen, man möchte ein Streckennetz zwischen drei Städten entwerfen, die in einem gleichseitigen Dreieck angeordnet sind. Man könnte ganz einfach Schienen von einer Stadt zur anderen legen und somit den Umfang des Dreiecks nachzeichnen. Wie sich aber herausstellt, gibt es eine bessere Lösung: Indem man eine vierte Haltestelle im Mittelpunkt des Dreiecks platziert und drei Schienen zu diesem Mittelpunkt führt. Dass der zweite Entwurf weniger Material für Schienen erfordert, lässt sich schnell überprüfen: Wenn die drei Städte jeweils einen Abstand von l haben, beträgt der Umfang des Dreiecks 3l. Im zweiten Szenario führt man die Schienen aber entlang der Winkelhalbierenden bis zum Mittelpunkt des Dreiecks. Diese Strecken haben eine Länge von jeweils ^√3⁄₃l. Damit hätte das Schienensystem im zweiten Fall eine Gesamtlänge von √3l: Das entspricht nur etwa 57 Prozent der Gesamtlänge im ersten Szenario.

Wenn man also zulässt, beim Bau der Haltestellen flexibel zu sein, kann man die Gesamtlänge der Netzwerkverbindungen deutlich reduzieren. Bei drei Punkten im Raum findet sich natürlich schnell der »Steinerbaum«, der die optimale Lösung darstellt – wobei man dem Netzwerk zusätzliche »Steiner-Punkte« hinzufügen muss. Aber je größer das zu Grunde liegende Problem ist, das heißt, je mehr Punkte man miteinander verbinden möchte, desto komplexer wird die Aufgabe. Tatsächlich lässt sich die Schwierigkeit, das Problem zu bewältigen, wissenschaftlich untersuchen.

Wie komplex darf es sein?

Das ermöglicht die Komplexitätstheorie, ein Teilbereich der theoretischen Informatik, bei dem es darum geht, Probleme in unterschiedliche Klassen einzuteilen: Dafür zieht man Algorithmen heran und ermittelt, wie die Anzahl der Rechenschritte mit der Größe der Aufgabe zusammenhängt. Während es zum Beispiel extrem schwer ist, eine große Zahl in ihre Primfaktoren zu zerlegen, ist es für Computer ein Leichtes, zu prüfen, ob eine Zahl eine Primzahl ist. Letzteres fällt nämlich in die Komplexitätsklasse von Problemen, die von theoretischen Informatikern mit »P« bezeichnet wird. Anschaulich ausgedrückt umfasst P all jene Probleme, die mit wachsender Größe immer noch effizient lösbar sind – die Anzahl der Rechenschritte wächst zwar mit der Größe der Aufgabe an, explodiert aber nicht. Etwas genauer: Die Rechendauer steigt bloß polynomiell mit der Größe der zu prüfenden Zahl n an, zum Beispiel mit n⁵. Solche Probleme sind von Computern in der Regel bewältigbar.

Bei einigen Problemen wächst die Rechendauer hingegen exponentiell an. Zwar kann jeder Computer sehr schnell die Zahl 15 in ihre Primfaktoren 3 und 5 zerlegen. Doch wenn Sie dem Rechner eine 150-stellige Zahl liefern, wird er vermutlich kapitulieren. Für Zahlentheoretiker ist das natürlich ärgerlich, für Kryptografen hingegen ein Segen: Denn anhand solcher komplexer Probleme können sie Verschlüsselungsverfahren entwerfen. Für diese Art von Aufgaben gibt es die Komplexitätsklasse »NP«. Vereinfacht ausgedrückt enthält sie alle Probleme, deren Lösung sich leicht (das heißt in polynomieller Zeit) überprüfen lässt. Das ist zum Beispiel bei der Primfaktorzerlegung der Fall: Es ist zwar extrem schwer, die Primfaktoren großer Zahlen zu berechnen, doch wenn man eine Lösung vorgesetzt bekommt, muss man sie nur miteinander multiplizieren, um das Ergebnis zu überprüfen. Die NP-Klasse enthält also alle Aufgaben aus P (da sie leicht zu lösen sind, ist ihre Lösung auch leicht prüfbar), aber darüber hinaus auch einige Probleme, die sich nur schwer berechnen lassen.

Nun steht und fällt die Definition der Komplexitätsklassen wie P und NP mit den Algorithmen, die man kennt, um gewisse Aufgaben zu lösen. Doch was, wenn jemand plötzlich einen völlig neuen Weg findet, um beispielsweise Primteiler einer Zahl zu berechnen – und die Rechendauer nur noch polynomiell mit der Größe der Zahl wächst? Solche Fragen bilden den Kern der theoretischen Informatik: Das größte ungelöste Rätsel besteht darin, herauszufinden, ob P und NP gleich sind. Sprich: Gibt es für alle Aufgaben, deren Lösung sich leicht überprüfen lässt, in Wirklichkeit einen effizienten Lösungsalgorithmus, den man bloß noch nicht kennt?

Das Steiner-Problem ist extrem komplex

Aber wie bestimmt man überhaupt, wie komplex ein Problem ist? Entscheidend ist dabei die Idee, Probleme aufeinander zu reduzieren. Sprich: Wenn jeder Algorithmus, der Aufgabe A löst, auch B lösen kann, dann ist B auf A reduzierbar. A ist damit komplexer als B. Die Informatiker Stephen A. Cook und Leonid Levin konnten Anfang der 1970er Jahre zeigen, dass es ein bestimmtes Problem in NP gibt, das so genannte »SAT«-Problem, auf das sich alle anderen NP-Aufgaben reduzieren lassen. Damit wäre SAT das schwerste Problem von NP. Wie sich allerdings herausstellte, ist es nicht das einzige: Es gibt weitere Aufgaben, auf die alle anderen NP-Probleme reduzierbar sind (darunter auch SAT): Man nennt solche Probleme NP-vollständig. Falls P und NP sich als ungleich herausstellen sollten, dann wären NP-vollständige Probleme sicher nicht in P enthalten. Für sie gäbe es dann keinen effizienten Lösungsalgorithmus, egal, wie lange man danach sucht. 1972 hat der Informatiker Richard Karp 21 Aufgaben identifiziert, die NP-vollständig sind – darunter eine vereinfachte Variante des Steiner-Problems.

Damit ist die Planung eines Schienennetzes mindestens (da Karp eine vereinfachte Variante des Steinerbaum-Problems untersucht hatte) so schwer wie ein NP-vollständiges Problem. Wenn man also viele Stationen miteinander verbinden möchte, kann die optimale Lösung sehr viel Rechenleistung erfordern. Glücklicherweise gibt es Näherungsverfahren, die uns einer optimalen Lösung zumindest nahe bringen. Tatsächlich können die besten Computerprogramme inzwischen Steinerbaumprobleme mit über einer Million Städten in wenigen Minuten in der Praxis lösen. Außerdem kann man das Problem in der Praxis vereinfachen, indem man beispielsweise die Anzahl der zusätzlich hinzugefügten Stationen (Steiner-Punkte) einschränkt. Schließlich möchte man bei einem Schienennetz, das 30 Städte verbinden soll, keine 60 zusätzlichen Umsteige-Bahnhöfe bauen.

Dennoch erfordert selbst die Planung eines vereinfachten Schienennetzes einiges an Rechenleistung und Zeit. Informatikerinnen und Informatiker mussten erst ausgeklügelte Algorithmen entwickeln sowie leistungsfähige Hardware bauen, um solche Aufgaben zu bewältigen. Umso erstaunlicher, dass der Schleimpilz Physarum polycephalum das Problem innerhalb weniger Stunden löst.

​​Was ist euer Lieblingsmathetheorem? Schreibt es gerne in die Kommentare – und vielleicht ist es schon bald das Thema dieser Kolumne!