Eine schwierige Rechenaufgabe ist für den Laien eine, für die er beim besten Willen keine Lösung findet. Für Mathematiker ist eine Aufgabe schwer, wenn zwar ein Lösungsweg bekannt ist, aber die Rechnung selbst auf dem schnellsten Computer länger dauern würde, als das Universum besteht.

Eine leichte Rechnung ist das schriftliche Multi-plizieren. Nimmt man zwei n-stellige Zahlen miteinander mal, muss man n mal n Ziffern multiplizieren und die Ergebnisse addieren. Macht zusammen n² Multiplikationen. Doppelt so lange Zahlen verlangen die vierfache Rechenzeit, dreimal so lange die neunfache. Selbst wenn die Rechenzeit mit n1000 wächst, finden Mathematiker das noch leicht. Sie sagen, das Problem lasse sich in "polynomialer Zeit" lösen, und nennen die Klasse dieser Probleme P.

Ein schweres Problem ist dagegen das folgende: Ein Müllwagen muss eine gewisse Zahl von Abfalleimern leeren. Welches ist der kürzeste Weg? Auf den ersten Blick ist die Lösung einfach: Man schaut sich alle möglichen Touren an und wählt die kürzeste aus. Nur wächst die Zahl der möglichen Routen nicht polynomial, sondern viel schneller: Wenn n+1 Tonnen zu leeren sind statt n, dann gibt es (n+1)-mal so viele Wege. Diese Zahl wächst für komplexe Touren schneller als jedes Polynom, auch schneller als n1000 oder n1000000. Das Routenproblem, auch "Problem des Handlungsreisenden" genannt, gehört zu einer Klasse von Problemen, die mit NP bezeichnet werden. Und die sind es, die Mathematiker schwer finden.

Wenn stures Ausprobieren nicht weit führt – gibt es vielleicht einen geschickteren Weg, um die kürzeste Tour zu finden? Ist das anscheinend schwere Problem also doch ein leichtes? Diese Frage wird mit der Gleichung "P=NP" umschrieben: Wenn sie stimmt, dann gehören die schweren und die leichten Rechnungen letztlich zur selben Liga. Wer die Frage beantwortet, kann reich werden. Die Clay Foundation zählt P=NP zu den "Millennium-Problemen" der Mathematik, für deren Lösung es jeweils eine Million Dollar gibt.

Weitere Artikel zur Serie "12 Fragen der Wissenschaft. Bitte klicken Sie auf das Bild.

Mastermind und Sudoku gehören dazu.

Die Müllauto-Frage gehört zu der interessanten Klasse von NP-Problemen, die sich durch eine seltsame Asymmetrie auszeichnen: Die Frage ist schwer – aber wenn einer eine Lösung anbietet, lässt sie sich auf "leichte" Weise überprüfen. Solche Probleme nennt man auch NP-vollständig, und für sie gilt: Wenn ein Problem in P liegt, dann gilt das für alle Probleme, und P ist tatsächlich gleich NP. Die Liste dieser Probleme umfasst mittlerweile über 3000 Fragen. Auch die Denkspiele

Das P=NP-Problem hat auch ganz praktische Auswirkungen. Verschlüsselungsalgorithmen basieren zum Beispiel darauf, dass man eine Zahl als Produkt zweier anderer darstellt. Eine solche Zerlegung zu ermitteln ist ein NP-Problem, während die Überprüfung einer gegebenen Zerlegung zu P gehört. Wäre P=NP, dann würden Geheimdienste und Banken überall auf der Welt um die Sicherheit ihrer Kommunikation fürchten.

Im Moment hat niemand eine Idee, wie sich die Frage beantworten ließe. Das erste Millennium-Problem, das vor zwei Jahren gelöst wurde, war seit mehr als 100 Jahren diskutiert worden. In einer Umfrage äußerten 61 von 100 Mathematikern die feste Überzeugung, dass P und NP tatsächlich verschieden sind. Aber Meinungen zählen in der Mathematik nicht – sie ist eine äußerst un- demokratische Wissenschaft.