Komplexitätstheorie

Die Komplexitätstheorie ist ein Teilgebiet der Informatik. Sie fragt nicht, ob ein Computer ein Problem lösen kann, sondern wie teuer das ist – gemessen in Zeit und Speicherbedarf. Beide Größen hängen davon ab, wie groß das Problem ist. Eine Liste mit zehn Einträgen zu sortieren dauert kurz; eine Liste mit einer Milliarde Einträgen dauert viel länger. Die Komplexitätstheorie beschreibt diesen Zusammenhang mathematisch genau und teilt Probleme in Klassen ein, je nachdem wie stark der Aufwand mit der Problemgröße wächst.

Warum manche Probleme praktisch unlösbar sind

Es gibt Probleme, für die kein Algorithmus bekannt ist, der sie schnell löst. Schnell bedeutet in der Komplexitätstheorie: Der Aufwand wächst höchstens als Polynom mit der Problemgröße – zum Beispiel quadratisch oder kubisch. Wächst er dagegen exponentiell, verdoppelt sich die Rechenzeit mit jedem zusätzlichen Element. Bei zwanzig Elementen ist das noch handhabbar, bei hundert bereits astronomisch.

Ein bekanntes Beispiel ist das Travelling-Salesman-Problem: Ein Handelsreisender soll alle Städte auf seiner Route genau einmal besuchen und dabei die kürzeste Gesamtstrecke wählen. Bei fünf Städten gibt es nur zwölf mögliche Routen. Bei zwanzig Städten sind es bereits über 60 Billionen. Kein Rechner der Welt kann alle davon durchprobieren, wenn die Zahl der Städte weiter steigt. Solche Probleme gelten als praktisch unlösbar – nicht weil Computer zu langsam gebaut werden, sondern weil die Mathematik dahinter es so festlegt.

Komplexitätsklassen: P, NP und das große offene Rätsel

Die bekanntesten Klassen heißen P und NP. In der Klasse P liegen Probleme, die ein Computer schnell lösen kann. In der Klasse NP liegen Probleme, bei denen man eine vorgeschlagene Lösung schnell prüfen, aber nicht unbedingt schnell selbst finden kann. Das Travelling-Salesman-Problem gehört zu NP: Ob eine bestimmte Route wirklich die kürzeste ist, lässt sich leicht nachrechnen – aber die kürzeste Route selbst zu finden, ist schwer.

Die offene Frage lautet: Ist P gleich NP? Also: Gibt es für jedes Problem, dessen Lösung sich schnell prüfen lässt, auch einen Algorithmus, der sie schnell findet? Die meisten Informatiker glauben, dass die Antwort Nein ist – bewiesen ist es bis heute nicht. Es ist eines der bekanntesten ungelösten Probleme der Mathematik, dotiert mit einer Million US-Dollar Preisgeld durch das Clay Mathematics Institute.

Daneben gibt es weitere Klassen, etwa PSPACE für Probleme mit begrenztem Speicherbedarf oder BQP für Probleme, die ein Quantencomputer effizient lösen kann. Diese Landkarte der Schwierigkeitsgrade ist das Kernstück der Komplexitätstheorie.

Bedeutung für KI, Kryptographie und Alltagsprodukte

Kryptographie – die Verschlüsselung von Daten – ist eines der wichtigsten Anwendungsgebiete. HTTPS, das Protokoll hinter jedem gesicherten Website-Aufruf, beruht darauf, dass bestimmte mathematische Probleme in NP liegen. Eine Zahl zu multiplizieren ist einfach; zwei große Primfaktoren einer riesigen Zahl zu finden, ist extrem schwer. Die Sicherheit moderner Verschlüsselung hängt buchstäblich daran, dass P ≠ NP gilt.

Auch in der KI spielt die Komplexitätstheorie eine Rolle. Viele Optimierungsprobleme – etwa das Trainieren neuronaler Netze oder das Planen von Routen in Navigations-Apps – sind NP-schwer. In der Praxis verwendet man deshalb Näherungsverfahren, sogenannte Heuristiken, die keine garantiert optimale, aber eine hinreichend gute Lösung in vertretbarer Zeit liefern. Google Maps findet in Sekunden eine sehr gute Route, aber nicht zwingend die mathematisch beste aller möglichen.

In Tech-News taucht die Komplexitätstheorie auf, wenn über Quantencomputer berichtet wird. Quantencomputer versprechen, bestimmte Probleme aus NP schneller zu lösen. Ob sie die Klasse P fundamental erweitern oder gar P = NP beweisen, ist aber offen. Wer solche Schlagzeilen einordnen will, braucht genau das Grundverständnis, das die Komplexitätstheorie liefert.