computerwoche.de

Archiv

Keiner weiß, ob das Resultat überhaupt stimmt:

Kombinatorische Probleme am Supercomputer

02.06.1989

Es wird immer wieder ein wenig bizarr, setzen statt braver Lohnbuchhalter oder Lagerverwalter ausgekochte Mathematiker sich an ein Computer-Terminal. Denn diese besondere Spezies Mensch liebt es geradezu, teure Supercomputer-Rechenzeit in Tausender-Stunden-Portionen zu vergeuden. Und findet es obendrein noch ganz natürlich, wenn sie am Ende nicht mal sicher weiß, ob überhaupt stimmt, was alles lange Rechnen da ergeben hat.

Extrem rechenaufwendige Probleme finden sich gleich zu Dutzenden in einer mathematischen Teildisziplin, die allgemein als Kombinatorik bekannt ist. Und da viele von jenen sich überhaupt erst sinnvoll bearbeiten lassen, seit der Mensch neben der Logik seines Gehirns auch noch die der schnellen Chips einsetzen kann, werden den Rechnern gerade aus dieser Ecke gern besonders vertrackte Aufgaben vorgelegt. Wie etwa auch jene, die einem gewissen Clement Lam jahrelang im Kopf umherging.

Einfache Problemstellung - schwierige Lösung

So schwierig Lams, in Kreisen erfahrener Kombinatoriker seit Jahren als ungelöst berühmtes Problem auch zu bearbeiten ist, so einfach kann man es seltsamerweise formulieren. Man muß sich dazu nämlich nur eine Matrix mit 111 Zeilen und 111 Spalten vorstellen, bei der in jeder Zeile exakt elf Plätze mit einer Markierung, also etwa mit einem Einser, belegt werden sollen; und zwar so, daß am Ende dann ganz von selber auch jede Spalte exakt elf Einser enthält. Doch während diese Forderung für sich allein ja noch einigermaßen leicht erfüllbar ist, wird die Sache durch eine zusätzliche schier unlösbar: Durch die Vorschrift nämlich, daß jedes später beliebig herausgegriffene Paar von zwei Zeilen der "fertigen" Matrix am Ende nur in jeweils einer einzigen Spalte mit den Markierungen übereinstimmen darf. Es dürfen also beispielsweise Zeile 17 und Zeile 56 bloß jeweils in Spalte 84 eine Markierung enthalten, während in sämtlichen anderen Spalten nur immer allein eine der beiden Zeilen einen Einser aufweisen darf.

Eine Anordnung der skizzierten Art wird in Kombinatoriker-Fachkreisen als "finite projektive Ebene" bezeichnet, und die Variante mit 111 Zeilen und Spalten würde, so sie in der Tat existierte, als der Ordnung Zehn zugehörig gelten. Doch wie Lam im Zuge seiner Computer-Studien inzwischen herausgefunden hat, existieren finite projektive Ebenen der Ordnung Zehn ganz einfach nicht - behauptet zumindest der Rechner. Und damit genügt offenbar keine aller denkbaren Kombinationen von Einsern und Nullern den oben skizzierten Forderungen.

Schon vor Heraufdämmern der Computer-Ära war Mathematikern klar geworden, daß finite projektive Ebenen oder auch einfach "Äquivalenz-Tafeln" immer dann einfach aufzustellen sind, wenn ihre Ordnung einer Primzahl wie 2 oder 3 oder 7 entspricht; oder aber, wie etwa 9 oder auch 27, der ganzzahligen Potenz einer Primzahl. Doch obwohl schon seit langem vermutet wird, Äqivalenz-Tafeln anderer Ordnungen als eben dargestellt existierten möglicherweise überhaupt nicht, ist niemand sich dieser Aussage sicher. Und auch Lams Erkenntnisse betreff en vorerst ja bloß den Spezialfall der Ordnung 10.

Wie dringend Computer benötigt werden, um diese und andere Aufgaben aus dem weiten Feld der Kombinatorik zu bearbeiten, zeigt allein schon die Tatsache, daß es für die Anordnung der Nuller und Einser nicht weniger als 470 Billionen (470.000.000.000.000) Möglichkeiten gibt. Doch diese 470 Billionen betreffen noch längst nicht etwa das gesamte Feld mit seinen 12.321 Matrix-Positionen, sondern nur die Zahl der Möglichkeiten, eine einzige Zeile mit elf Einsern zu belegen.

Hundert Jahre und kein Ende

Manuell auszuprobieren, ob es für die skizzierte Belegungsweise eine Lösung gibt oder nicht, schied also auf jeden Fall aus. Doch auch Versuche aus dem Jahre 1979, bei denen Lam übrigens mit einer VAX arbeitete, endeten zunächst in blanker Hoffnungslosigkeit. Denn es zeigte sich bald, daß die VAX trotz ihrer, für damals, stolzen Geschwindigkeit mehr als 100 Jahre brauchen würde, ehe Lams Erben auf ein Resultat hoffen konnten. Und deshalb blieb am Ende nur noch die Hoffnung auf Gratis-Rechenzeit an einem Supercomputer.

So eine Maschine wurde Lam schließlich in Princeton zugänglich gemacht; und zwar in Gestalt der Cray des dortigen Instituts für militärische Analysen. Der junge Kombinatoriker von der Montrealer Concordia-Universität durfte diesen schnellen Rechner allerdings immer nur dann für sich beanspruchen, wenn die Militärs gerade mal wieder kein Problem sahen und der Rechner daher müßig war; doch auch so kamen im Laufe der Zeit mehrere Tausend Stunden kostbarer Cray-Rechenzeit zusammen. Was rein kalkulatorisch immerhin dem Gegenwert von mehreren Millionen Dollar entsprechen soll, wie Lam sich einmal mit leichtem Gruseln ausmalte.

Resultat noch rätselhafter als die Problemstellung

Interessant ist mit Blick auf die Frage, ob es finite projektive Ebenen der Ordnung 10 denn nun wirklich nicht gibt - oder, trotz Lam und Cray, vielleicht doch - vor allem eines: Nach all' der aufwendigen Suche ist das Resultat an sich nun selber schon eher ein Rätsel als eine klare Aussage. Denn nur jene Mathematiker, die mit der Schreibweise der diversen Rechner-Ausdrucke wirklich vertraut sind, haben ja überhaupt eine Chance, das Ergebnis intellektuell nachzuvollziehen.

Und was die ganze Sache trotz oder vielleicht auch gerade wegen des immensen Aufwands noch ein weiteres bißchen undurchschaubarer macht, ist die Tatsache, daß derzeit auch keinerlei reelle Chance besteht, Lams Ergebnis "einfach" mit Hilfe eines anderen Riesen-Rechners nachzuprüfen. Und dies nicht etwa allein aus Kosten- und Zeit-Gründen, sondern auch, weil Lams Programm gleich von mehreren Informatikern gemeinsam erarbeitet worden ist, die dabei alle ganz spezielle Eigenheiten mit eingebracht haben und deren Ideen für Außenstehende nicht unbedingt leicht nachvollziehbar sein dürften. Und außerdem wurden die Berechnungen sehr Hardwarenahe ausgeführt.

Ein weiteres Problem im Zusammenhang mit Lams Resultat besteht darin, daß Rechner bekanntlich nicht unfehlbar sind und Störungen aller Art - von Alphateilchen infolge kosmischer Strahlung bis zu Macken im Betriebssystem - einen an sich geordneten Rechengang spürbar durcheinanderbringen können.

Das sieht übrigens auch Lam selber, der daher freimütig einräumt: Für ihn sei die ganze Arbeit nicht eigentlich ein mathematischer Beweis im strengen, eindeutigen Sinne dieses Worts; sondern eher eine Art mathematischen Experiments, das daher irgendwann wiederholt werden sollte. Wie dies von physikalischen Experimenten - die eine Theorie ja nie beweisen, sondern höchstens mal widerlegen können - doch auch gefordert werden muß.

Ergebnis nicht nur für Mathematiker interessant

Ironischerweise ist es am Ende der ganzen Geschichte übrigens nun doch wieder rein menschliches "Zu-Fuß-Denken", was in den letzten Wochen das Vertrauen in Lams Programm - und außerdem in die Maschine, die es bearbeitet hat - stärkte.

Denn als Lam mit Hilfe seiner Algorithmen bei einem weiteren Experiment feststellte, es gebe exakt nur vier verschiedene Anordnungs-Muster, mit denen man finite projektive Flächen der Ordung Neun zustande bringen könne - da stimmte sein Ergebnis gut mit dem bisherigen Stand des Wissens überein. Denn auch Mathematiker hatten bei allem "manuellem" Sinnieren bislang nur vier Muster herausgefunden.

Am Ende schließlich stellt sich bei Unternehmungen der hier beschrieben Art immer wieder die Frage: Lohnt so ein Ergebnis die ganzen Mühen und die - zumindest theoretisch - vergeudeten Rechner-Ressourcen denn überhaupt? Und hätte man den Computer denn nicht besser mit etwas "Nützlichem" beschäftigt?

Es liegt auf der Hand, daß Mathematiker und insbesondere Kombinatoriker größte Mühe haben dürften, allein auch nur den Sinn so einer provokanten Frage zu verstehen.

Doch alle anderen mag in diesem Kontext Lams Feststellung beruhigen, die gleichen Algorithmen und Rechentechniken, die hier für scheinbar Nutzloses erarbeitet und erprobt worden sind, ließen sich auch auf vielen anderen Gebieten der Kombinatorik nutzbringend anwenden. Und zwar in Bereichen von durchaus praktischem "Nährwert, denn aus ihnen lassen sich beispielsweise Antworten auf höchst lebensnahe Fragestellungen der modernen Kommunikationstechnik ableiten.

So etwa auch Antworten auf die Frage, wie man die zentralen Schalt- und Verteilknoten hochmoderner Glasfaser-Nachrichtennetze möglichst geschickt aufbauen kann. Also in einer Weise, daß sie, trotz minimalen Aufwands, doch allen Anforderungen der Praxis von entsprechen werden.