Alois Potton hat das Wort [Nr. : 19, 06/1995 ]


 

Komplexitätstheorie

 

Aufwandsabschätzungen machen Sinn. Das schönste Konzept taugt nichts, wenn es wegen unzureichender Berücksichtigung wichtiger Parameter wie Kosten, Laufzeit,... nicht funktioniert. Es ist also angebracht, sich bereits beim Systementwurf über die zu erwartende Komplexität der Realisierung Gedanken zu machen. Unsere Studierenden beschäftigen sich leider meist nur selten oder gar nicht mit solchen Aufwandsüberlegungen - z.B. haben sie (überraschenderweise?) häufig kein Gespür für Kosten. Viele spätere Fehlentscheidungen sind auf diesen Mangel zurückzuführen.

Bedauerlicherweise wird die Disziplin der Komplexitätstheorie, die sich mit diesen Fragen beschäftigt, von vielen gestandenen Praktikern etwas despektierlich betrachtet. Dies mag auf eine gewisse (Ehr-)Furcht vor ihrer mathematischen Schwierigkeit zurückgehen, vielleicht ist es aber auch eine Folge von fragwürdigen Auswüchsen. Ein besonders seltsames Beispiel zweifelhafter komplexitätstheoretischer Fingerübungen ist Gegenstand des vorliegenden Beitrags. Der Vorfall trug sich zu anläßlich der Begehung eines größeren Forschungsprojekts (apropos "Begehung": diese Wortwahl stimmt mit dem wahren Ablauf nur unzureichend überein, es sollte besser "Be-Sitzung" oder "Be-Kaffeetrinkung" heißen).

Es ging um Parallelrechnersysteme - und da spielen komplexitätstheoretische Fragen eine wichtige Rolle. Man möchte wissen, welche Leistungssteigerung durch Kopplung von Rechnern erreicht werden kann - und dabei interessiert man sich für den Abhängigkeit des Leistungsverhaltens von der Problemgröße, d.h. ob und wie sich die Leistung mit steigender Rechnerzahl n verbessert. Daß hier ein entscheidender Unterschied z.B. zwischen linearen bzw. quadratischen Abhängigkeiten besteht, liegt auf der Hand. Demgegenüber sind konstante Faktoren oft nachrangig: Ob der Aufwand 2n oder 85.346n ist, das ist dem Komplexitätstheoretiker schnurz und piepe, weil ihn in erster Linie der generelle Verlauf der Aufwandsfunktion interessiert - und da sind konstante Faktoren gegenüber z.B. quadratischem Wachstum für genügend große Rechnerzahlen unerheblich.

Einer der Mitarbeiter, der anläßlich der genannten Begehung einen Bericht über seine Forschungstätigkeit gab, stellte eine beeindruckende Zahl neuer Ergebnisse vor. Eines davon führte unter der Bezeichnung "Zeitverlust" einen Wert O(log*nlogloglogn) auf. Dabei bezeichnet n die Zahl eingesetzter Rechner, und der Buchstabe "O" steht für "größenordnungsmäßig", also (vereinfacht gesprochen) für: "bis auf konstante Faktoren und ähnliche Dreckeffekte". Auch die Mehrfachlogarithmierungen sind für denjenigen, der sich ein wenig mit solchen Fragen beschäftigt hat, mit einigem Nachdenken nachvollziehbar: Solches liegt an baumartigen Zusammenschaltungen, an Fallunterscheidungen etc. Soweit so gut. Fehlt nur noch der mir damals (wie wohl auch den meisten Lesern) unbekannte Term log*n. Auf die entsprechende Frage antwortete der Vortragende, das sei die Anzahl von Logarithmierungen zur Basis 2, die man ausführen müsse, um von n aus den Wert 1 zu erreichen. Also ist z.B. log*16 = 3, und auch im Falle log*n = 4 ist n noch halbwegs überschaubar, nämlich 65.500 und ein paar kaputte; eine so große Rechnerzahl ist bei gutem Willen noch vorstellbar. Ab dann wird's aber geradezu abenteuerlich: Für log*n = 5 gilt bereits n = "2 hoch 65.536", und diese Zahl ist so gewaltig, daß sie nur noch mit der geschätzen Zahl der Atome im gesamten Universum verglichen werden kann. Wenn man also aus jedem Atome des Universums einen Rechner basteln könnte, dann käme gerade mal ein Term "5" im obigen Ausdruck vor. Bei nur wenig größeren Werten, also z.B. log*n = 6, beginnen sich die Nackenhaare zu sträuben (2 hoch Zahl der Atome des Universums!?). Man kann sich die Größe dieser Zahl vorstellen und auch wieder nicht, ist das nicht interessant? Es ist also festzustellen, daß die genannte Formel für log*n eigentlich nur Werte zwischen 1 und 5 anbietet (wobei 1 bis 3 noch recht uninteressant sind und 5 bereits jenseits von Gut und Böse liegt). Somit könnte also der Term log*n in der genannten Formel durch eine kleine Konstante, z.B. durch 4, ersetzt werden, und diese könnte man sofort weglassen, weil es ja (wie das große O besagt) auf konstante Faktoren nicht ankommt. Aber Fragen nach dem Sinn eines Terms log*n, der für alle denkbaren Situationen völlig irrelevant ist, werden von Komplexitätsleuten als unzulässig erklärt: Der Term sei korrekt; man interessiere sich nur für Strukturen, nicht aber für die konkrete Realisierbarkeit. Kommentar am Rande: vielleicht deshalb, weil man sich dann die Finger schmutzig machen würde?

 

Nach meiner Auffassung kommen solche Spielereien inzwischen allzu häufig vor (die Zahl der Atome des Universums wird auf ziemlich lange Zeit deutlich höher sein als die Zahl baubarer Rechner!). Wohlgemerkt, ich plädiere keineswegs für irgendeine Art von "Zensur": Man darf über solche und größere Systeme sicher nachdenken, aber welchen Sinn machen "Ergebnisse", die erst bei nachweislich unerreichbaren Größenordnungen gegenüber konventionellen Lösungen Vorteile versprechen? Auch wenn sie formal korrekt sind: Sind solche Resultate noch als "richtig" zu bezeichnen? Muß man sie nicht eher kontraproduktiv oder sogar kinderverderbend nennen?

Vielleicht droht der Informations- und Kommunikationstechnik auch eine Entwicklung wie der Mathematik vor einem knappen Jahrhundert (ich verdanke diesen Hinweis Prof. Sigram Schindler; hallo Sigi!): Ausgehend von sehr konkreten Problemen ("wieviele Kühe passen auf eine Wiese? Rechne!" oder "wie bestimmt man den Ostertermin für die nächsten 200 Jahre?") hat sich damals ein großer Teil der Mathematik hin zur Erforschung mehr oder weniger wertfreier Resultate verselbständigt. Dies hatte (und hat) zudem noch den Vorteil, daß diese "Spieltriebresultate" eleganter und genialischer wirken als diejenigen, welche sich auf konkrete Dinge beziehen - und daß sie auch irgendwie leichter erzeugt werden können.

Der Wert oder die "Haltbarkeit" solcher Spieltriebsresultate kann aber nach meiner Auffassung durchaus charakterisiert werden mit dem handschriftlichen Zusatz, den ich kürzlich am Eingang eines Ramschladens über einem Stapel Hundefutter angebracht fand; er hieß: "Abfülldatum ist Verfalldatum".


In diesem Sinne
Ihr Alois Potton