Die Zeit
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 …
