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.