A4/Wie schwierig ist Rechnen

Aus QuaNTH
Wechseln zu: Navigation, Suche

A4

Rechnen
Einführung

Lektionen


Nachdem wir nun die Grundstrukturen eines Rechners definiert und ein Beispiel gegeben haben, wollen wir uns mit dem beschäftigen, was der Rechner tun soll, nämlich dem Lösen von Aufgaben. Hierbei bezieht sich der Begriff "lösen" auf das Durchlaufen eines vorgefertigten Programms - ob dieses Programm dann wirklich ein bestimmtes Problem löst, ist unerheblich.

Das Halteproblem

Es gibt bei der Vorstellung des "Durchlaufens" eines Programms einen Sonderfall, nämlich kann es passieren, dass ein Programm (bzw. ein Algorithmus) kein Ende findet. Gibt man einem Rechner z.B. die Aufgabe, sämtliche natürlichen Zahlen aufzulisten, so wird er dies solange tun, bis ihm sein endlicher Speicher zum Anhalten zwingt. Ebenso kann ein Programm in eine endlose Schleife steuern, das heißt, dass er nicht von selbst zu einem Ende findet. Ob ein bestimmter Algorithmus nach endlicher Zeit endet, ist i.A. nicht feststellbar. In der theoretischen Informatik nennt man dieses Problem auch das Halteproblem. Im Jahr 1937 zeigte A. Turing, dass es keinen algorithmischen Weg gibt, das Halteproblem allgemein zu entscheiden. Wir werden uns im Folgenden jedoch nicht mit den Feinheiten dieses Problems beschäftigen, sondern immer annehmen, dass die betrachteten Programme nach endlicher Zeit zu einem Ergebnis kommen.

Leichte und schwierige Aufgaben

Um zu definieren, welche Aufgaben leicht oder schwer sind, bemerkt man zunächst, dass so eine Unterscheidung natürlich nur für Aufgabentypen, nicht für spezielle Instanzen sinnvoll ist. Also geht es nicht darum, ob "3 + 5" eine schwierige Aufgabe ist, sondern ob "Addition" schwierig oder leicht ist.

Um das Beispiel zu diskutieren, erinnere man sich zunächst daran, wie man die Addition lernt. Zuerst lernt man, wie man die Zahlen bis 10 addiert, dann die einstelligen Zahlen mit Übertrag. Schließlich lernt man das Verfahren des schriftlichen Addierens und bemerkt hierbei, dass es kaum einen Unterschied macht, ob man Zahlen, die im Hunderterbereich oder Tausenderbereich liegen, addiert. Um zwei Zahlen mit N Stellen zu addieren, muss man bei der schriftlichen Addition nur N mal eine Addition mit Übertrag ausführen. Somit erhöht sich der Aufwand beim Addieren beim Vergrößern des Zahlenraums nur langsam - wann immer man die Größe der zu addierenden Zahlen um den Faktor 10 vergrößert, braucht man einen zusätzlichen Additionsschritt. Dieses Verhalten werden wir später zur Definition der Klasse der einfachen Aufgaben benutzen.

Betrachten wir ein komplizierteres Beispiel: die Zerlegung in Primzahlen. Hier besteht die Aufgabe darin, bei einer Zahl mit N Ziffern einen Teiler dieser Zahl zu bestimmen. Wie würde man hier vorgehen? Der naive Ansatz wäre, sämtliche möglichen Teiler der Reihe nach zu versuchen. Wenn die Zahl den Wert x hat, muss man hierfür höchstens x/2 Kandidaten durchprobieren. Nun hat aber eine Zahl mit N Ziffern einen Wert von etwa x \approx 10^N, wenn man also sämtliche Teiler durchprobieren möchte, braucht man 10^Z/2 Versuche.

Wir sehen einen entscheidenden Unterschied zwischen den beiden Problemen: Im ersten Fall muss man nur einen Schritt mehr ausführen, wenn man die Eingangszahlen um eine Ziffer verlängert, während man im zweiten Fall 10 mal so lange braucht. Genau dieses Verhalten unterscheidet einfache von schwierigen Aufgaben. Wenn die benötigte Zahl der Schritte höchstens wie ein Polynom der Eingangsgröße (im Beispiel linear) wächst, heißt das Problem einfach, wenn sie schneller als jedes Polynom, also exponentiell schnell wächst, heißt das Problem schwierig.

Abschließend bemerken wir noch, dass die Einordnung eines Problems in leicht oder schwierig vom besten bekannten Verfahren abhängt. Sollte ein Verfahren zur Zerlegung in Primfaktoren gefunden werden, das deutlich schneller ist als das oben angegebene naive Verfahren, so müsste man das Problem "Faktorisierung" auch in die Klasse der leichten Probleme stecken. Viele der Erkenntnisse der theoretischen Informatik deuten darauf hin, dass es solch ein besseres Verfahren nicht gibt, aber ein theoretischer Beweis, dass es solch ein Verfahren nicht geben kann steht noch aus. Wir werden auf diesen Problemkreis noch im Kapitel B.4 näher eingehen, wenn wir die hier nur angedeuteten Komplexitätsklassen formal definieren.

Verbindung zu Quantensystemen

Wie wir bereits in der Einleitung erwähnt haben, ist die Simulation von Quantensystemen mit klassischen Rechnern sehr aufwendig, also ein schwieriges Problem nach der obigen Definition. Dies bedeutet konkret, dass eine Vergrößerung des zu simulierenden Quantensystems einen exponentiellen Anstieg der zur Simulation benötigten Ressourcen zur Folge hat. Wir werden als nächstes beschreiben, wie man dies ausnutzen kann, um Computer zu bauen, für die einige der Probleme, die klassisch "schwer" sind, mit Hilfe der Quantenmechanik "einfach" werden.

An dieser Stelle sollten wir noch anmerken, dass die Tatsache, dass für ein bestimmtes Problem keine einfache Lösung bekannt ist, nicht immer ein Nachteil sein muss. In der klassischen Kryptographie benutzt man gerade schwierige Probleme, um so genannte Pseudo-Einwegfunktionen zu konstruieren, die einen wichtigen Baustein der Verschlüsselung darstellt (siehe auch Kapitel B.3). Wäre es möglich, das schwierige Problem zu lösen, könnte hierdurch die verwendete Verschlüsselung gebrochen werden. So wäre ein Quantencomputer beispielsweise in der Lage, die im Internet übliche RSA-Verschlüsselung durch das schnelle Auffinden von Primfaktoren zu knacken.