Aber die kürzeste Verbindung zwischen zwei Punkten ist doch eine Gerade!" schrie Friedrich Spanner aufgebracht.

"Das bestreite ich ja nicht", entgegnete Franz Steiner ruhig. "Ich meine nur, daß wir nicht unbedingt alle Knoten in die Städte legen müssen, die vernetzt werden sollen."

"Und wo wollen Sie dann all diese Extrapunkte hinlegen?"

"Das ist genau meine Frage."

Die Oberpfälzer Infobahn GmbH, eine neue Firma mit großen Plänen und knapper Kapitaldecke, wollte Vohenstrauß, Tirschenreuth und Pressath durch Glasfaserkabel verbinden. Nur konnten sich die beiden Chefs nicht über die Strategie einigen. Spanner meinte, es sei am besten, eine Stadt herauszugreifen und von dort zu den beiden anderen Kabel in gerader Linie zu verlegen.

"Welche Stadt?" fragte Steiner.

"Das hängt von den Entfernungen ab, ist aber gar nicht schwer zu entscheiden. Von dem Dreieck aus den drei Städten streiche man die längste Seite weg und lege Kabel entlang den beiden anderen Seiten."

"Klingt vernünftig. Aber..." Steiner hatte die vage Vorstellung, die Gesamtlänge würde sich noch verkürzen lassen, wenn man eine vierte Stadt mit in das Netz aufnähme. Das ist auf den ersten Blick zwar nicht besonders einleuchtend; wenn er aber recht hätte, wo müßte der zusätzliche Knotenpunkt liegen, und wieviel Kabellänge könnte man damit einsparen?

Vohenstrauß, Tirschenreuth und Pressath sind jeweils ungefähr 30 Kilometer voneinander entfernt (Bild 1). Spanners Netzwerk wäre – unter Weglassung der Direktverbindung Pressath-Vohenstrauß – 57 Kilometer lang. Wie steht es nun mit Steiners windiger Idee? Ungefähr in der Mitte des Dreiecks, am Ufer des Flüßchens Waldnaab, liegt eine Ansiedlung mit vielsagendem Namen ungefähr 15 bis 18 Kilometer von jeder der drei Städte entfernt.

"Schauen Sie sich das an, Herr Spanner. Mitteldorf. Wenn wir einen Knotenpunkt dorthin legen und Leitungen zu allen drei Städten..."

"Quatsch! Mehr Knoten heißt mehr Kabel."

"Eben nicht. Kann man ausrechnen. Eine Leitung von Mitteldorf aus zu jeder Stadt macht zusammen – Moment, haben wir gleich – 52,2 statt 57 Kilometer nach Ihrer Methode. Das sind achteinhalb Prozent weniger."

Spanner schaute ungläubig auf die Karte, kratzte sich am Kopf und gab sich schließlich geschlagen. Das Faxgerät piepte, aber sie achteten nicht darauf.

"Ich überlege gerade: Man kann sich die gleiche Frage für jede beliebige Menge von Städten stellen", fuhr Steiner fort. "Wie lang ist das kürzeste Netzwerk, das jede mit jeder verbindet, wenn alle Knotenpunkte in den gegebenen Städten liegen müssen? Und wie sieht das kürzeste Netzwerk aus, wenn wir uns die Freiheit nehmen, irgendwo weitere Knoten anzulegen?"

Spanner hatte etwas Entscheidendes begriffen: "Wenn man mehr Möglichkeiten zur Auswahl hat, kann das Optimum nur besser werden. Schließlich sind wir ja nicht gezwungen, neue Knoten einzuführen. Aber um wieviel besser?"

Während Steiner entschwand, um in einer Datenbank nach einer Antwort zu suchen, rief Spanner nach der Sekretärin, weil sich die eingehenden Faxe zu türmen begannen. Es wäre ihm nicht eingefallen, sie selber zu sortieren.

Einige Stunden später kam Steiner zurück. "Wir sind nicht die ersten, die sich diese Fragen stellen. Es gibt sogar eine große Menge Literatur dazu. Edgar Gilbert und Henry Pollak von den AT&T Bell-Laboratorien in Murray Hill (New Jersey) haben 1968 folgende Vermutung aufgestellt: Einerlei, wie die Städte liegen, kann man durch Einführen zusätzlicher Knotenpunkte nicht mehr als 13,4 Prozent der Kabellänge einsparen. Man spricht von der Vermutung zum Steinerschen Verhältnis oder auch von der Steiner ratio conjecture."

"Was haben Sie für ein Verhältnis?"

"Nicht ich. Jakob Steiner." Nach einem kurzen Blick auf die mitgebrachten Zettel: "Mathematiker aus Bern. 1796 bis 1863."

"Und warum sagt man nicht Gilbert-Pollak-Vermutung?"

"Das liegt an den Zuschreibungsgewohnheiten der Mathematiker."

"Und die besagen?"

"Benenne die Idee nach einem bereits verstorbenen Menschen, der sie zwar nicht hatte, aber irgendwie vage damit befaßt war. Jedenfalls ist es keine Vermutung mehr, sondern der Satz vom Steinerschen Verhältnis..."

"Satz von Gilbert-Pollak", beharrte Spanner.

"Eigentlich wäre ,Satz von Du und Hwang' die korrekte Bezeichnung. Denn 1991, nach 23 Jahren unnachgiebiger, aber weitgehend unergiebiger Anstrengungen haben Ding-Zhu Du von der Universität Princeton und Frank Hwang von den Bell-Laboratorien die Vermutung bewiesen" (Spektrum der Wissenschaft, November 1991, Seite 26).

Spanner stieg gedankenverloren über den Haufen Faxpapier und holte sich eine Tasse längst erkalteten Kaffees. "Ach so. AT&T ist eine Telephongesellschaft, da ist das naheliegend."


Gerüste und Steiner-Bäume

"Dazu gibt es eine interessante Geschichte, aber die erzähle ich Ihnen später. Wichtig ist zunächst, wie ich bei meiner Recherche gelernt habe, die Sache mathematisch sauber zu formulieren. Wir denken uns die zu verbindenden Städte als Punkte in einer Ebene und die Verbindungskabel als gerade Strecken. Ob wir nun neue Verbindungsknoten einführen oder nicht – unser Netz aus Punkten und Strecken muß auf jeden Fall einen sogenannten Baum bilden. Das heißt, es darf kein geschlossener Rundweg entstehen; denn sonst gäbe es ja zwei verschiedene Verbindungen zwischen zwei Punkten, und von denen könnte man eine weglassen. Ein solches Netz, das jede Stadt mit jeder auf genau eine Weise verbindet, ohne neue Knotenpunkte einzuführen, heißt aufspannender Baum oder auch Gerüst. Es gibt viele mögliche Gerüste zu einer gegebenen Menge von Städten, aber im Prinzip könnte man sie alle auflisten und unter ihnen das kürzeste auswählen."

Nehmen wir beispielsweise Ahlen, Bochum, Coesfeld und Dülmen. Bild 2 zeigt einige Gerüste und deren Gesamtlängen. Bei dem kürzesten gehen von einem Verzweigungspunkt in Dülmen Verbindungen zu den anderen drei Städten aus. Für Ahaus, Bergkamen, Coesfeld und Dülmen hingegen, die annähernd auf einer Geraden liegen, besteht der kürzeste aufspannende Baum aus der Verbindung Ahaus-Coesfeld-Dülmen-Bergkamen, in dieser Reihenfolge, und hat keinen Verzweigungspunkt.

Das Problem ist viel komplizierter, wenn die Kabel sich auch außerhalb der Städte verzweigen dürfen. Das kürzeste Netzwerk zwischen Tirschenreuth, Pressath und Vohenstrauß beispielsweise ist dasjenige, das alle drei mit Mitteldorf – genauer: einem namenlosen Punkt zwischen Mitteldorf, Kotzenbach und Rotzendorf – verbindet. Im allgemeinen muß das kürzeste Netzwerk, das eine gegebene Menge von Städten verbindet, ebenfalls ein Baum sein, der sogenannte Steiner-Baum (Spektrum der Wissenschaft, März 1989, Seite 78).

"Wer war eigentlich dieser Steiner?" unterbrach Spanner, als sein Kollege mit der Erklärung so weit gekommen war. "Was hat er mit dem Problem zu tun?"

"Nicht allzuviel", erwiderte Steiner. "Er hat halt 1837 das Problem für drei Städte gelöst. Richard Courant und Herbert Robbins haben seinen Namen 1941 in ihrem klassischen populären Buch ,Was ist Mathematik?' mit dem Problem verbunden. Weder diese beiden noch Steiner scheinen gewußt zu haben, daß Evangelista Torricelli" - wieder ein Blick auf den Spickzettel – "1608 bis 1647, und Bonaventura Cavalieri, 1598 bis 1647, ihm schon 1640 zuvorgekommen waren." Steiner wußte, daß Spanner ein Faible für historische Daten hatte.

"War dieser Torricelli nicht der Typ, der das Barometer erfunden hat?"

"Eben der. Und Cavalieri war einer der Urväter der modernen Infinitesimalrechnung. Die beiden haben zwei Fälle unterschieden. Wenn einer der Winkel des Dreiecks 120 Grad oder größer ist, besteht das kürzeste Netzwerk aus den zwei Dreiecksseiten, die dieser stumpfen Ecke anliegen. Im anderen Falle besteht es aus den drei Strecken, die von den drei Städten aus zu dem sogenannten Steiner-Punkt laufen. Das ist der eindeutig bestimmte Punkt, an dem sich diese drei Verbindungen unter einem Winkel von jeweils 120 Grad treffen" (Bild 3).

Steiner fuhr fort, seinen Namensvetter zu preisen. "Auch bei mehr als drei Städten müssen sich die Kanten des Steiner-Baumes in jedem neu eingeführten Knoten unter 120 Grad treffen. Das ist nicht besonders schwer zu sehen und wurde ebenfalls von Steiner bewiesen. Wesentlich schwerer ist es, einen solchen Baum tatsächlich zu finden. Die ersten ernsthaften Untersuchungen dazu stammen von Milos Kössler und Vojtech Jarník aus dem Jahre 1934."

"Es leuchtet ein, daß das nicht einfach ist", erwiderte Spanner. "Man muß ja ei-ne ungeheure Menge denkbarer Steiner-Punkte in Betracht ziehen."

"Sie haben es erfaßt. Stellen Sie sich zum Beispiel sechs Städte in den Ecken zweier benachbarter Quadrate vor. Einen Steiner-Baum für ein einzelnes Quadrat zu finden ist nicht schwer. Dann bleibt noch, die zwei verbleibenden Städte des anderen Quadrats anzuhängen; das ist auch nicht schwer" (Bild 4 a).

"Aha. Ist das nun ein Steiner-Baum?"

"Ja."

"Also ist es das optimale Netzwerk?"

"Nein."

"Aber Sie haben mir doch gerade gesagt, daß die kürzesten Netzwerke Steiner-Bäume heißen."

"Diese Mathematiker verallgemeinern manchmal so schnell, daß man kaum mitkommt. Man nennt ein Netz einen Steiner-Baum, wenn jeder neu eingeführte Knoten aus drei Kanten mit Winkeln von 120 Grad besteht. Also: Jeder optimale Baum ist ein Steiner-Baum, aber nicht umgekehrt."

"Aha. Und was Sie da gezeichnet haben, ist der optimale Steiner-Baum?" (Bild 4b)

"Ein optimaler Steiner-Baum."

"Also der mit der kürzesten Länge?"

"Einer von zwei gleich langen optimalen. Den anderen bekommen Sie durch Spiegelung an der horizontalen Mittellinie."

"Spitzfindigkeiten."

"Jedenfalls sieht man an dem Beispiel, daß man kürzeste Steiner-Bäume nicht schrittweise, eine Stadt nach der anderen einbeziehend, konstruieren kann."

"Das sehe ich ein", sagte Spanner, rief zwischendurch abermals barsch – und erfolglos – nach der Sekretärin und fragte weiter: "Was haben Gilbert und Pollak nun getan?"

"Sie fragten sich, was die Länge eines minimalen aufspannenden Baums und die eines optimalen Steiner-Baums miteinander zu tun haben. Nennen wir die erste Größe die Gerüstlänge der Städte und die zweite die Steiner-Länge. Nun ist jedes Gerüst auch ein Steiner-Baum."

"Wieso? Ich denke, Steiner-Baum ist, wenn in jedem neu eingeführten Knoten..."

"Wir führen aber keine neuen Knoten ein."

"Also ist die Bedingung trivialerweise erfüllt?"

"Richtig."

"Was soll dann diese Spielerei mit Worten?"

"Ganz einfach: Für jede gegebene Menge von Städten ist die Gerüstlänge stets größer oder gleich der Steiner-Länge; denn die ist definiert als die Länge des kürzesten unter allen Steiner-Bäumen. Die Frage ist: Wie groß kann der Unterschied sein?"


Der klassische Steiner-Baum

"Na schön", erwiderte Spanner, "nehmen wir als Beispiel zum Probieren ein gleichseitiges Dreieck mit Seitenlänge 1. Dann beträgt die Gerüstlänge 2 und die Steiner-Länge ." "Genau", stimmte Steiner zu. "In diesem Fall beträgt also das Verhältnis von Steiner-Länge zu Gerüstlänge . Und das heißt, daß..." "... die Einsparung an Länge, wenn man den kürzesten Steiner-Baum statt des kürzesten Gerüsts nimmt, ungefähr 13,4 Prozent beträgt." "Sie sind ein kluges Kerlchen. Aber Sie brauchen sich nichts darauf einzubilden. Gilbert und Pollak haben nun vermutet, daß man unter keinen Umständen mehr einsparen könne. Einerlei, wie viele Städte es sind und wie sie liegen, stets ist das Verhältnis von Steiner-Länge zu Gerüstlänge größer oder gleich " "Sie meinen, die Längenersparnis, die man durch die Verwendung eines kürzesten Steiner-Baumes statt eines kürzesten Gerüstes erreichen kann, ist niemals mehr als 13,4 Prozent?" "So lautet die Vermutung." "Nehmen wir an, wir wissen, wieviel eine Verkabelung entlang den Strecken eines kürzesten Gerüstes kostet. Dann wäre es also sinnlos, mehr als 13,4 Prozent dieser Summe für den Versuch aufzuwenden, einen kürzesten Steiner-Baum zu berechnen?" "Ja." Ähnliche, wenn auch in der Praxis kompliziertere Probleme stellen sich bei Gasleitungen, Fernsehkabeln, Buslinien, Eisenbahnstrecken oder Flugverbindungen und – scheinbar weit hergeholt – bei Theorien zur biologischen Evolution. Die genetische Information eines Lebewesens steckt in seiner DNA, codiert durch eine Folge aus dem Sortiment der vier Basen Adenin, Thymin, Cytosin und Guanin. Eine solche Folge würde beispielsweise als AATTCGCTCA... geschrieben. Man identifiziere die DNA-Sequenz eines Organismus mit einer Stadt und den – geeignet quantifizierten – Unterschied zweier Sequenzen mit der Entfernung der beiden Städte. Der Steiner-Punkt von drei solchen Sequenzen ist dann der wahrscheinlichste gemeinsame Vorfahr, genauer: unter allen potentiellen gemeinsamen Vorfahren derjenige, für den man die geringste Gesamtanzahl an Mutationen unterstellen muß. Diesen Vorfahr muß es nicht wirklich gegeben haben; dennoch liefert diese Methode Hinweise darauf, wie die DNA-Moleküle sich verändert haben könnten und wie eng oder weitläufig die Organismen verwandt sind. Eine Vielzahl weiterer Fragen hat immerhin Analogien zum Steiner-Baum-Problem; die wichtigste betrifft den Entwurf elektronischer Schaltungen. Hier legt man die Verbindungen meist entlang den Linien eines Rechteckgitters, also nur horizontal oder vertikal. Aber es gibt Fragen – und Antworten – der gleichen Art wie bei Steiner-Bäumen. Die Vermutung zum Steiner-Verhältnis ist wichtig, wenn die Kosten der Berechnung relevant sind, denn wir werden gleich sehen, daß es viel einfacher ist, ein kürzestes Gerüst zu bestimmen als einen kürzesten Steiner-Baum. Es könnte also billiger sein, zugunsten eines geringeren Rechenaufwands eine Materialverschwendung von 13,4 Prozent in Kauf zu nehmen. "Wissen Sie", sagte Steiner, "wenn AT&T eine Nebenstellenanlage für die verstreuten Büros einer Firma einrichtete, nahm man bis vor kurzem die Gerüstlänge als Maßstab für den Preis. Ein Kunde hätte also mit Hilfe imaginärer Büros in Steiner-Punkten die Rechnung drücken können. Die Vermutung begrenzt solche potentiellen Einsparungen nun auf 13,4 Prozent, und das ist für den Anbieter nicht allzu peinlich." "Warum haben die Leute von AT&T sich diese Sorgen nicht erspart, indem sie selbst die Steiner-Länge zugrunde legten?" fragte Spanner. "Konnten sie nicht." "Warum nicht?" Steiner seufzte. "Die Gerüstlänge zu bestimmen ist einfach, selbst für eine riesige Anzahl Städte. Man beginnt mit der kürzesten Verbindung zwischen irgend zwei Städten, die man finden kann. Danach fügt man stets die kürzestmögliche Verbindung zwischen irgend zwei noch unverbundenen Städten hinzu, die keine Schleife erzeugt, und fährt so fort, bis alle Städte miteinander verbunden sind" (Bild 5). "Und das funktioniert?" "Immer. Das Verfahren heißt übrigens gieriger Algorithmus." "Was ist ein Algorithmus?" "Ein genau bestimmtes Verfahren, das ein Computer ausführen kann und das garantiert die gesuchte Lösung liefert." "Wir könnten einen Algorithmus gebrauchen, der die Sekretärin wiederfindet – wir haben hier mittlerweile ungefähr 20 Kilometer Faxpapier. Na gut. Warum heißt der Algorithmus gierig?" "Gierige Algorithmen nehmen in jedem Schritt das größte Stück, das sie kriegen können, wenn es darum geht, eine möglichst große Gesamtsumme aufzuhäufen. Das ist manchmal ungünstig. Wer sich zunächst mit bescheidenen Gewinnen begnügt oder auch einmal einen Verlust in Kauf nimmt, kann am Ende viel besser abschneiden" (Spektrum der Wissenschaft, März 1993, Seite 42). "In diesem Fall", fuhr Steiner fort, "ist Gier zweckmäßig. Es geht zwar darum, etwas zu minimieren statt zu maximieren, aber die Idee ist eigentlich die gleiche. Also nimmt man denselben Namen." "Er müßte eigentlich asketischer Algorithmus heißen", wandte Spanner ein. "Na schön. Und wie funktioniert der Algorithmus zur Bestimmung kürzester Steiner-Bäume?" "Das ist es ja gerade", erwiderte Steiner verdrießlich. "Das ist sehr schwer." "Kann man nicht jeweils drei Städte zusammenfassen, deren Steiner-Punkt bestimmen und dann...?" "Eben nicht. Schon für ein so einfaches System wie vier Städte in den Ecken eines Quadrats sind solche Punkte nicht Steiner-Punkte für irgendeine Teilmenge von drei Städten" (Bild 4). "Ach so. Und die Ebene enthält unendlich viele Punkte." "In der Tat. Obwohl die meisten für die Lösung vermutlich nicht in Frage kommen, ist es gar nicht klar, daß es überhaupt Algorithmen gibt, die in endlicher Zeit die Lösung finden." "Und? Gibt es welche?" "Ja. Den ersten hat Zdzislaw A. Melzak von der Universität von British Columbia in Vancouver (Kanada) erfunden. Aber seine Methode ist nicht wirklich praktikabel. Sie wird schon für mäßige Städtezahlen extrem aufwendig. Inzwischen ist sie verbessert worden, aber nicht entscheidend." Spanner starrte den immer noch wachsenden Faxhaufen an und schüttelte sich wie ein Hund, der aus dem Wasser kommt. "Warum ist das so schwer?" Steiner lehnte sich in seinem Sessel zurück und machte eine ausladende Geste. "Dafür gibt es, ausgelöst durch die zunehmende Nutzung der Computer, eine herrliche neue Theorie, die Komplexitätstheorie. Sie untersucht nicht nur einzelne Algorithmen, sondern insbesondere deren Effizienz" (Spektrum der Wissenschaft, April 1994, Seite 64). "Effizienz habe ich schon einmal gehört. Ist das eine dieser neuartigen Management-Strategien?"

Leichte und schwere Probleme

"Bleiben wir mal bei der Theorie", sagte Steiner. "Nehmen wir an, ein Problem ist gegeben, in das irgendeine Anzahl n von Objekten (bei uns Städten) eingeht. Wie stark wächst dann die Laufzeit eines Algorithmus zur Lösung des Problems mit wachsendem n an? Wenn diese Zeit nicht schneller wächst als ein festes Vielfaches einer festen Potenz von n, sagen wir oder , dann sagt man, der Algorithmus läuft in polynomialer Zeit. Und Probleme, für die es solche Algorithmen gibt, betrachtet man als ,leicht'. In der Praxis ist der Algorithmus dann meistens brauchbar, es sei denn, die Konstante oder der Exponent wären wirklich riesig. Wenn aber die Laufzeit schneller wächst als polynomial, zum Beispiel exponentiell wie oder , dann ist der Algorithmus in der Praxis meistens unbrauchbar. Und Probleme, für die es nur solche Algorithmen gibt, nennt man ,schwer'." "Geben Sie mir ein paar Beispiele." "Na gut. Die Addition zweier n-stelliger Zahlen erfordert einschließlich der Überträge höchstens 2n Ziffernadditionen. Jede dieser Elementaroperationen läßt sich in einer konstanten Zeit ausführen. Also ist die Zeit zur Addition zweier n-stelliger Zahlen ein konstantes Vielfaches (hier 2) der ersten Potenz von n. Die gewöhnliche Schulmethode der Multiplikation zweier solcher Zahlen benötigt etwa Ziffernmultiplikationen und nicht mehr als Additionen, also Ziffernoperationen. Die Schranke enthält also nur die zweite Potenz von n. Schulkinder mögen es anders sehen, aber diese Probleme gelten als leicht." "Verstanden." "Gut. Betrachten wir dagegen das Problem des Handlungsreisenden: Finde die kürzeste Route, die einen Vertreter durch eine vorgeschriebene Menge von Städten und zurück zum Ausgangspunkt führt. Wenn es n Städte gibt, dann beträgt die Anzahl der Routen, die in Betracht kommen, n!=n(n-1)(n-2)x...x3x2x1, und das wächst schneller als jede Potenz von n. Alle Wege durchzuprobieren wäre also hoffnungslos ineffizient." Spanner stimmte zu und fragte: "Was ist im Bereich zwischen polynomialer und exponentieller Zeit?" "Da ist ein Niemandsland von ,verhältnismäßig einfachen' oder auch ,mäßig schwierigen' Problemen. Ob Lösungsverfahren dafür praktisch brauchbar sind oder nicht, ist eine Frage der Erfahrung." "Aha." "Verrückterweise ist es das größte Problem der Komplexitätstheorie, zu beweisen, daß es überhaupt interessante Probleme gibt, die wirklich schwer sind." "Wie wäre es mit der Beantwortung aller dieser Fax-Nachrichten? Das wird von Minute zu Minute exponentiell schwerer." "Ach was. Wenn man das Sortieren geschickt anstellt, ist der Aufwand n mal Logarithmus von n. Das ist leicht. Und das Antworten? Je mehr man liegen läßt, desto mehr erledigt sich von selbst. Aber im Ernst: Die Schwierigkeit liegt darin, daß es leicht ist zu zeigen, daß ein Problem leicht ist, aber schwer, daß es schwer ist. Wenn man zu einem Problem einen einzigen Algorithmus angeben kann, der es in polynomialer Zeit löst, hat man bewiesen, daß das Problem leicht ist. Es muß nicht der beste Algorithmus sein – irgendeiner genügt. Aber ein Algorithmus, der ein Problem in nicht-polynomialer Zeit löst, sagt noch nichts darüber, ob das Problem schwer ist. Vielleicht hat man nur einen ungeschickten Algorithmus gewählt. Man muß alle überhaupt nur möglichen Algorithmen zur Lösung des Problems betrachten und zeigen, daß keiner davon in polynomialer Zeit läuft." "Das sehe ich ein. Gibt es wenigstens Vermutungen darüber, was ein schweres Problem ist?" "Zum Beispiel das Problem des Handlungsreisenden. Oder das Packungs-Problem: Wie kann man Gegenstände mit bestimmten Abmessungen in möglichst wenige Behälter mit gegebenen Abmessungen packen? Oder das Rucksack-Problem: Gegeben ein Rucksack und viele Gegenstände, läßt sich der Rucksack mit einer Auswahl der Gegenstände lückenlos füllen? Aber bisher hat niemand zeigen können, daß irgendeines dieser Probleme wirklich schwer ist. Immerhin gelangte Stephen Cook von der Universität Toronto in Kanada 1971 zu einem wichtigen Ergebnis: Wenn ein Problem in dieser Gruppe schwer ist, dann gilt das für alle anderen auch; denn man kann jedes so umformulieren, daß es zu einem Spezialfall eines anderen Problems derselben Gruppe wird. Diese Klasse nennt man NP-vollständig, wobei NP für ,nicht-deterministisch polynomial' steht. Alle Experten meinen, diese Probleme seien wirklich schwer." "Warum?" "Wahrscheinlich aus psychologischen Gründen. Man kann einfach nicht glauben, daß es für alle die Probleme aus dieser großen Klasse eine unentdeckte Wunderwaffe geben soll. Jedenfalls haben Ron Graham, Michael Garey und David Johnson von AT&T gezeigt, daß das Problem der Steiner-Bäume NP-vollständig ist. Ein effizienter Algorithmus zur Bestimmung der genauen Steiner-Länge für jede gegebene Menge von Städten wäre also eine Wunderwaffe." "Also läßt sich alles, was wir über Algorithmen wissen wollen, auf ein spezielles Problem in Kommunikationsnetzen zurückführen", sagte Spanner erstaunt. "So ist es. Oder auf eines von Tausenden anderer Probleme. Lösen Sie eines, und Sie haben sie alle. Die Vermutung zum Steiner-Verhältnis ist auch wichtig, weil sie zeigt, daß man anstelle eines schweren Problems ein leichtes lösen kann, ohne allzuviel zu verlieren. Und das bedeutet, daß die Methoden zum Beweis der Vermutung auch wichtig sind." "Was sind das für Methoden?"

Der Beweis

"Für das gleichseitige Dreieck, mit dem alles begann, gibt es eine recht natürliche Lösung. Das legt nahe, daß es einen einfachen Beweis der Vermutung geben müßte. Aber wenn es den gibt, dann hat ihn bisher niemand gefunden. Die Einfachheit des Spezialfalls ist also irreführend. Selbst der Beweis von Du und Hwang ist ziemlich trickreich. Wer es für kleine Anzahlen mit direkten Methoden versucht, versinkt in einem Wust von Formeln. Gilbert und Pollak hatten für ihre Vermutung zahlreiche Hinweise; sie vermochten zum Beispiel zu zeigen, daß das Steiner-Verhältnis stets mindestens 0,5 beträgt. Um 1990 hatten diverse Leute durch heroische Rechnungen die Vermutung für Netze mit 4, 5 und 6 Städten bestätigt. Für beliebig viele Städte war die untere Abschätzung für das Verhältnis nacheinander von 0,5 auf 0,57, 0,74 und schließlich auf 0,8 angehoben worden. Vor einigen Jahren verbesserten Graham und Fang Chung von den Bell-Laboratorien die Schranke auf 0,824. Die dazu erforderliche Rechnung nannten sie selber ,fürchterlich'. Es war deutlich geworden, daß dies der falsche Weg war." "Sehr hilfreich", meinte Spanner in einem Anflug von Sarkasmus. "Lästern Sie nicht. Das war vielleicht hilfreicher, als Sie denken. Dadurch wurde die Aufmerksamkeit auf abstraktere Methoden gelenkt. Weitere Fortschritte waren nur zu erwarten, wenn man die fürchterlichen Rechnungen vereinfachen könnte. Es gelang Du und Hwang, sie vollständig zu umgehen. Die Grundfrage ist: Wie bringt man gleichseitige Dreiecke ins Spiel? Für die weiß man alles, aber von da bis zu einer allgemeinen Anordnung von Städten, die derselben Schranke genügen soll, klafft eine Riesenlücke. Wie kann man dieses Niemandsland durchqueren?" "Wollen wir darauf nicht lieber erst eingehen, wenn alle diese Faxe beantwortet sind?" "Ach, warten Sie noch einen Moment. Dies hier ist wirklich unglaublich faszinierend. Es gibt eine Art Zwischenstation im Niemandsland. Stellen Sie sich die Ebene eingeteilt in lauter gleichseitige Dreiecke vor, also ein reguläres Dreiecksgitter. Städte setzen wir nur in die Ecken dieser Dreiecke. Es stellt sich heraus, daß dann als Kandidaten für Steiner-Punkte lediglich die Mittelpunkte der Dreiecke in Frage kommen. Kurz gesagt, wir haben jetzt viel mehr Überblick, nicht nur über die Rechnung, sondern auch über die theoretische Untersuchung" (Bild 6). "Wundervoll. Aber normalerweise liegen Städte nicht auf den Ecken eines Dreiecksgitters." "Doch. Jedenfalls die, auf die es wirklich ankommt. Das haben Du und Hwang gezeigt. Nehmen wir an, die Vermutung wäre falsch. Dann muß es ein Gegenbeispiel geben: irgendeine Anordnung von Städten, für die das Verhältnis kleiner als ist. Sie fanden heraus: Wenn es ein solches Gegenbeispiel gibt, dann muß es auch eines geben, dessen Städte sämtlich auf einem solchen Dreiecksgitter liegen. Dadurch kommt nun eine Regelmäßigkeit in die Sache hinein, und der Rest ist relativ einfach." Spanner dachte einen Augenblick nach. "Gut, aber wie haben sie bewiesen, daß es reicht, die Vermutung für das Gitter zu verifizieren?" "Eine wunderbare Übung im lateralen Denken. Zuerst machten sie aus der Vermutung ein Minimax-Problem aus der Spieltheorie. John von Neumann und Oskar Morgenstern haben sie erfunden und 1947 in ihrem klassischen Werk ,Theory of Games and Economic Behavior' veröffentlicht. Zwei Spieler treten gegeneinander an und versuchen, den maximalen Gewinn des Gegners zu minimieren. In dem Spiel von Du und Hwang wählt ein Spieler die ungefähre Form des Steiner-Baumes und der andere den kürzesten Steiner-Baum dieser Form, den er finden kann. Die Auszahlungsfunktion dieses Spiels hat eine spezielle Eigenschaft namens Konvexität. Damit bewiesen Du und Hwang, daß es zu einem beliebigen Gegenbeispiel eines auf dem Gitter geben muß. Diese elegante neue Methode erledigt eine Frage, die zuvor völlig unangreifbar schien, schlägt quasi eine Schneise durch einen Dschungel von Berechnungen und Fallunterscheidungen und liefert eine saubere, konzeptionell einfache Lösung. Sie ist nicht einfach und setzt eine gewisse mathematische Kunstfertigkeit voraus. Aber sie ist eine so dramatische Verbesserung, daß sie alle früheren Ansätze deklassiert. Wichtiger noch: Sie liefert einen Ansatz zur Untersuchung analoger Fragen. Man formuliere das Problem in der Sprache der Spieltheorie, beweise eine geeignete Konvexitätseigenschaft und führe es so auf eine Frage zurück, für deren Lösung es viel weniger Möglichkeiten gibt. Dann löse man das reduzierte Problem – wie auch immer – und ist fertig. Die Maxime ,erst denken, dann rechnen' sollte jedem Mathematiker tief ins Gehirn graviert sein." Ergriffen von der so eindrucksvoll demonstrierten Schönheit der Theorie wandte sich Spanner dann doch der Praxis zu und wühlte sich durch den Berg an Faxen. Plötzlich brach er in gottlose Flüche aus. "Was ist?" "Eines dieser unbeantworteten Faxe ist vom Stadtrat von Tirschenreuth. Sie haben entschieden, daß wir den Auftrag für die Vernetzung mit Pressath und Vohenstrauß nicht bekommen." Steiners Miene verdüsterte sich. "Warum nicht?" Spanner knurrte ihn an: "AT&T hat uns um 13,4 Prozent unterboten."

Literaturhinweise

- Was ist Mathematik? Von Richard Courant und Herbert Robbins. 4. Auflage. Springer, Heidelberg 1992.

– Mathemagische Tricks. Von Martin Gardner. Vieweg, Braunschweig 1981.

– Steiner Minimal Trees. Von Edgar N. Gilbert und Henry O. Pollak in: SIAM Journal of Applied Mathematics, Band 16, Seiten 1 bis 29, 1968.

– Companion to Concrete Mathematics. Von Z. A. Melzak. Wiley, New York 1973.

– Studentenfutter. 100 Aufgaben für Mathe-Feinschmecker. Von Hugo Steinhaus. Urania, Leipzig 1991.

– Steiner Problems in Networks: A Survey. Von Pawel Winter in: Networks, Band 17, Seiten 129 bis 167, 1987.


Aus: Spektrum der Wissenschaft 4 / 1995, Seite 10
© Spektrum der Wissenschaft Verlagsgesellschaft mbH