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.
Not eines Handlungsreisenden
Die meisten Aufgaben aus der Schulmathematik - addieren, potenzieren, Wurzeln ziehen, Gleichungen lösen - sind in diesem Sinne einfach. Die Addition zweier fünfstelliger Zahlen etwa lässt sich in fünf Additionen von Ziffern mit gegebenenfalls einem Übertrag aufspalten. Sollen zwei hundertstellige Zahlen zusammengezählt werden, so genügen hundert Rechenoperationen.
Bei der Multiplikation entsteht schon mehr Aufwand. Sollen zwei fünfstellige Zahlen multipliziert werden, sind dazu 25 Multiplikationen und Additionen von Ziffern nötig. Bei hundertstelligen Zahlen sind es bereits 10.000 Multiplikationen und Additionen. Die Anzahl der Rechenoperationen wächst hier mit dem Quadrat der Stellen der zu multiplizierenden Zahlen.
Das ist zwar komplizierter als bei Additionen, aber harmlos im Vergleich zum Handlungsreisenden. Probiert man da alle Routen durch, so sind das bei fünf Städten 30 Möglichkeiten, bei zehn Städten schon 3.628.800 und bei 100 zu besuchenden Orten schon mehr Kombinationen als es Atome im gesamten Universum gibt. Zumindest mit der naiven Herangehensweise, alle Routen durchzuprobieren, explodiert der Rechenaufwand.
Aber womöglich gibt es ja ein geschicktes Verfahren, um die Sache abzukürzen. Würde es gefunden, gehörte nicht nur der Handlungsreisende zur einfachen Klassen der p-Probleme, sondern mit ihm Hunderte anderer Optimierungsaufgaben, unter anderem die der Einkaufstasche, der Hausfrau und des Mobilfunks.
Es gälte p=np. Alle Aufgaben aus der np-Klasse wären auf relativ einfache p-Probleme reduziert. Das wäre eine Sensation, und jeden Cent des Millionen-Dollar-Preisgeldes wert. Die Industrie würde enorm profitieren, da sich wichtige Aufgaben aus der Praxis in kurzer Zeit lösen ließen. Banken hingegen wären über Nacht in großer Not.
"Nniemand hat eine gute Idee"
Denn die Verschlüsselung von Kreditkartennummern im Internet zum Beispiel kann nur deswegen nicht geknackt werden, weil es so aufwändig ist, eine große - etwa eine 200-stellige - Zahl in ihre Faktoren zu zerlegen. 35 ist 7 mal 5, das weiß jedes Schulkind. Schwieriger wird es schon bei 758.717. Das ist 761 mal 997. Bei Zahlen mit mehr als hundert Stellen ist die Suche aussichtslos. Eine Zahl in ihre Teiler zu zerlegen, zählt bislang zu den Aufgaben aus der np-Klasse.
Aber vielleicht findet ja ein genialer Kopf ein effizientes Rechenverfahren, das große Zahlen in ihre Teiler aufspaltet. Damit wäre zugleich p=np nachgewiesen und viele heute als komplex geltende Probleme auf lösbare Aufgaben reduziert. Die wissenschaftliche Gemeinde ist jedoch skeptisch. "Man muss ehrlich zugeben, dass weltweit im Augenblick niemand eine gute Idee hat, wie man das p=np-Problem lösen kann", sagt der Berliner Mathe-Professor Grötschel.
Die meisten Fachleute sind sogar überzeugt, dass p nicht gleich np ist. Um diese Behauptung zu belegen, müsste man aber beweisen, dass es keine effiziente Lösung für die np-Probleme gibt. Und der Nachweis, dass etwas nicht existiert, ist nicht nur bei Ufos und Telepathie vertrackt, sondern auch in der Mathematik. "Jede Menge falsche Beweise, nicht nur von Laien, pflastern diesen Weg", sagt Grötschel. "Viel Schweiß und bisher kein Erfolg."
Der Geldverkehr im Internet bleibt somit zumindest von dieser Seite her sicher. Und der arme Handlungsreisende wird noch so manche Irrfahrt in Kauf nehmen müssen.