Kann man die Schwierigkeit mathematischer Probleme messen?

Manche Menschen glauben, Mathematik sei grundsätzlich kompliziert und alle in der Mathematik vorkommenden Aufgaben seien einfach unmenschlich schwierig.

Man kann aber durchaus Probleme unterschiedlicher Schwierigkeit voneinander unterscheiden, und zwar nicht nur aufgrund subjektiven Empfindens, sondern durchaus anhand objektiver Kriterien.

So lässt sich die Schwierigkeit eines Problems oder einer Aufgabe messen, indem man fragt: Wie lange braucht man zur Lösung dieses Problems?

Wir betrachten zunächst Aufgaben, die oft gar nicht als «Problem» angesehen werden, die aber in der Mathematik laufend auftreten, zum Beispiel das Addieren und Multiplizieren von Zahlen. Dabei soll es jetzt nicht um die psychologische Schwierigkeit einer Einzelaufgabe («7 mal 8» ist schwieriger als «3 mal 4»), sondern um die Aufgabe des Multiplizierens als solche gehen.

Konkret lautet die Frage: Wie groß ist der Aufwand, um zwei Zahlen miteinander zu multiplizieren? Das kommt natürlich auf die Größe der Zahlen an. Wir messen die Größe einer Zahl durch die Anzahl ihrer Stellen: Dreistellige Zahlen sind schwieriger zu multiplizieren als zweistellige. Wir wissen, dass wir die Multiplikation großer Zahlen auf viele Multiplikationen aus dem kleinen Einmaleins zurückführen können. Und genau darauf kommt es an, auf die Anzahl der Multiplikationen aus dem kleinen Einmaleins, die man benötigt, um zwei Zahlen zu multiplizieren. Dies ist ein faires Maß für den Arbeitsaufwand.

Um zwei dreistellige Zahlen zu multiplizieren, braucht man maximal neun Multiplikationen mit dem kleinen Einmaleins. Denn man multipliziert jede Ziffer der zweiten Zahl mit jeder Ziffer der ersten, und das gibt drei mal drei, also neun Multiplikationen. Die Additionen werden als besonders einfach angesehen, deshalb lässt man sie bei der Aufwandabschätzung unter den Tisch fallen.

Um zwei vierstellige Zahlen zu multiplizieren, benötigt man maximal 16 Multiplikationen, und wenn man zwei n-stellige Zahlen multipliziert, reichen maximal n² Multiplikationen aus dem Einmaleins. Damit haben wir ein Maß für den Aufwand der Multiplikation von Zahlen gewonnen.

Wann immer man einen Aufwand erhält, der als n², n³, n¹⁰ - oder allgemein als n^k - beschrieben werden kann, spricht man von «polynomiellen» Problemen (weil der Aufwand durch ein Polynom wie n^k angegeben wird). Dies sind die «einfachen» Probleme. Viele Probleme der Mathematik sind in diesem Sinne einfach: Addieren, Multiplizieren, Suchen, Sortieren, Multiplizieren von Matrizen usw.

Es gibt aber auch ganz andere Aufgaben, ungleich schwierigere Probleme, solche, die einen unglaublichen Aufwand erfordern. Dies sind Probleme mit «exponentiellem» Aufwand. Bei denen lautet die Formel für den Aufwand 2ⁿ oder 10ⁿ oder so ähnlich - jedenfalls steht das n im Exponenten.

Wir können uns folgendes Problem vorstellen: In einer «mathematischen Lotterie» wird eine n-stellige Zahl gezogen. Um sicher zu sein, den Hauptgewinn zu erhalten, muss man alle Zahlen tippen, das sind 10ⁿ viele. Dies ist ein Beispiel für ein exponentielles Problem.

Ein weiteres exponentielles Problem ist die Rückwärtssuche im Telefonbuch: Angenommen, Sie haben nur ein Telefonbuch, aber keinen Computer und kein Telefon zur Verfügung. Wie lange brauchen Sie, um zu einer gegebenen Nummer den Namen zu finden?

Exponentielle Probleme sind Probleme ohne intelligente Abkürzung, bei denen einem nichts anderes übrig bleibt, als alle Möglichkeiten durchzuprobieren.