Wer auf dem schnellsten Weg von Augsburg nach Zwickau will, gibt heutzutage die beiden Orte ins Navigationssystem ein und erhält binnen Sekunden die optimale Route. Sollen auf dem Weg noch Berlin, Chemnitz, Düsseldorf und Erfurt in dieser Reihenfolge angefahren werden, ist auch das für die Elektronik kein Problem. Sie berechnet erst den besten Weg von Augsburg nach Berlin, dann die Strecke von Berlin nach Chemnitz und so fort.
Will ein Reisender eine möglichst effektive Tour durch 26 deutsche Städte absolvieren, sind die schnellsten Computer der Welt mit der Reiseplanung überfordert.
(Foto: Foto: dpa)Knifflig wird es, wenn mehrere Städte besucht werden sollen, und zwar in beliebiger Reihenfolge, aber auf dem kürzesten Gesamtweg. Will ein Reisender zum Beispiel eine möglichst effektive Tour durch 26 deutsche Städte von Augsburg bis Zwickau absolvieren, sind die schnellsten Computer der Welt mit der Reiseplanung heillos überfordert.
Selbst wenn es zwischen den Städten immer nur eine Verbindung gibt, sind über 400 Quadrillionen Routen (eine Quadrillion ist eine Eins gefolgt von 24 Nullen) möglich. Das ist auch für Elektronenhirne eine unbeherrschbare Zahl.
Brächte man tausend Routenpläne auf einer Schreibmaschinenseite unter und legte die Seiten aufeinander, ergäbe sich ein Papierturm, der bis zum Doppelstern Alpha Centauri aufragte. Ein effektives Verfahren, um solche Rechenprobleme zu lösen, ohne alle möglichen Varianten einzeln durchzuprobieren, ist bis heute nicht bekannt.
"Das Problem des Handlungsreisenden"
Fachkreise nennen diese Aufgabe "das Problem des Handlungsreisenden". In der Realität taucht es indes weniger in der Logistikbranche auf als zum Beispiel beim Bestücken von Computerchips oder dem Steuern einer Werkzeugmaschine.
Eine Methode, einen optimalen Ablauf mit vielen Zwischenstationen zu finden, würde sich für die Industrie lohnen. Und: Wer das Problem des Handlungsreisenden löst, bekommt von der amerikanischen Clay Foundation ein Preisgeld von einer Million Dollar.
Sollte eines Tages jemand dieses Problem lösen, ließen sich damit - nach vergleichsweise simplen Anpassungen - zugleich mehrere hundert weitere mathematische Aufgaben bewältigen.
"Verwandte Probleme treten nahezu überall auf, ob in der Telekommunikation, bei der Organisation von Abläufen in Produktion, Transport oder Verkehr oder dem Chipdesign", sagt Martin Grötschel, Professor am Konrad-Zuse-Zentrum für Informationstechnik Berlin. Einige von diesen besprechen Wissenschaftler in diesen Tagen in Budapest auf der Konferenz "Building bridges between mathematics and computer science", die Grötschel mitorganisiert hat. Drei Beispiele:
Beim Einkaufen im Supermarkt sollen die Waren so auf zwei Taschen verteilt werden, dass diese gleich schwer sind.
Binnen drei Stunden will die Hausfrau die Wohnung putzen, einkaufen, ein Drei-Gänge-Menu kochen, duschen, sich festlich kleiden und schminken. Welche Reihenfolge ist die günstigste?
Ein Unternehmen plant ein neues Mobilfunknetz mit 10.000 Antennen und 100 verschiedenen Frequenzen. Lässt sich das so einrichten, dass alle benachbarte Antennen auf verschiedenen Frequenzen senden?
Jedes dieser Probleme ist bis heute mathematisch nicht lösbar, und so verschieden die Aufgaben erscheinen: Sie haben große Ähnlichkeiten. Alle werden sie umso komplizierter, je größer die Zahl der Eingaben ist. Um fünf Waren möglichst gleichmäßig auf zwei Taschen zu verteilen, lassen sich noch alle Möglichkeiten durchprobieren.
Bei hundert Artikeln kostet das viel Zeit, bei 100.000 wird es unmöglich. Ebenso ist der Ablauf im Haushalt umso schwieriger, je mehr Tätigkeiten zusammenkommen, und das Telekommunikationsunternehmen muss umso mehr grübeln, je mehr Antennen und Frequenzen zu verteilen sind.
Mehr Kombinationen als Atome im Universum
Zudem ist es bei allen drei Problemen viel schwieriger, eine Lösung zu finden, als zu entscheiden, ob eine vorgegebene Lösung die richtige ist. Um letzteres zu entscheiden muss man beipielsweise nur die Taschen auf eine Waage stellen oder den Plan für die Antennen einmal genau durchsehen.
Das erinnert an ein Puzzle: Mit einem Blick lässt sich sagen, ob es fertig und korrekt zusammengesetzt ist. Aber die ungeordneten Teile richtig zusammenzufügen erfordert viel Zeit und Geduld. Auch beim Problem des Handlungsreisenden ist es für Mathematiker ein Leichtes, festzustellen, ob eine bestimmte Route die kürzeste ist.
Eine Aufgabe, bei der es verhältnismäßig einfach ist herauszufinden, ob eine Lösung die beste ist, bezeichnen Mathematiker als "np-Problem". Unter ihnen gibt es schwierigere als die genannten Beispiele und relativ einfache wie die simple Addition zweier Zahlen. Letztere werden mit dem Kürzel p benannt.
Was "einfach" und "schwierig" bedeutet, haben Mathematiker klar festgelegt. Hat eine Aufgabe aus n Eingaben (Orte, Antennen, Waren...), so lassen sich einfache Probleme in einer Zahl von Rechenschritten erledigen, die sich als eine Potenz von n schreiben lässt, also in n² oder n³ Rechenschritten. Bei schwierigen Aufgaben ist das nicht möglich. Hier wächst der Rechenaufwand ins Unermessliche.