Komplexitätstheorie — Wie schwer ist ein Problem?

Einführung

Kannst du in einer Liste von Millionen Zahlen in unter einer Sekunde die größte finden? Ja — einfach alle einmal durchgehen. Kannst du in derselben Zeit die kürzeste Route durch 1.000 Städte finden, die jede genau einmal besucht? Nein — zumindest mit bekannten Methoden nicht.

Das ist kein Softwareproblem. Das ist ein fundamentales Problem der Informatik. Manche Probleme sind einfach schwer — nicht weil unsere Computer zu langsam sind, sondern weil die Anzahl möglicher Lösungen exponentiell mit der Eingabegröße wächst.

Die Komplexitätstheorie untersucht, wie viel Rechenaufwand Probleme grundsätzlich benötigen. Sie unterscheidet zwischen Problemen, die effizient lösbar sind, und solchen, die es nicht sind — und fragt, ob es einen fundamentalen Unterschied zwischen diesen Klassen gibt. Die Antwort auf diese Frage ist eines der größten offenen Probleme der Mathematik.

Grundidee

Ein Algorithmus braucht Ressourcen: Rechenzeit und Speicher. Wie stark diese Ressourcen mit wachsender Eingabegröße n wachsen, beschreibt die Komplexität.

Die O-Notation drückt das asymptotisch aus: Sie sagt, wie der Aufwand wächst, wenn n sehr groß wird — und ignoriert konstante Faktoren. Ein Algorithmus mit Laufzeit 5n² und einer mit 2n² sind beide O(n²) — für die grundlegende Einschätzung ist das wichtig genug.

Erklärung

O-Notation: Die wichtigsten Klassen

O(1) — Konstant: Der Aufwand ist unabhängig von n. Beispiel: Indexzugriff auf ein Array, HashMap-Lookup. Bei n = 1 oder n = 1.000.000: immer gleich schnell.

O(log n) — Logarithmisch: Der Aufwand wächst extrem langsam. Beispiel: Binäre Suche. log₂(1.000.000) ≈ 20 — aus einer Million Elementen findet man eins in 20 Schritten.

O(n) — Linear: Der Aufwand wächst proportional zu n. Beispiel: Lineare Suche, einmaliges Durchlaufen einer Liste. Doppelt so viele Elemente → doppelt so viel Aufwand.

O(n log n) — Linearithmisch: Wächst etwas schneller als linear. Beispiel: Mergesort, Quicksort im Durchschnitt. Der „sweet spot” für viele praktische Algorithmen.

O(n²) — Quadratisch: Der Aufwand wächst mit dem Quadrat von n. Beispiel: Bubblesort, naive Matrizenmultiplikation. Doppelt so viele Elemente → viermal so viel Aufwand. Bei großen n sehr langsam.

O(2^n) — Exponentiell: Verdoppelt sich bei jedem zusätzlichen Element. Beispiel: Alle Teilmengen aufzählen, naive Lösung vieler Optimierungsprobleme. Bei n = 30: eine Milliarde Operationen. Bei n = 60: schon mehr als alle Sandkörner der Erde.

O(n!) — Faktoriell: Für Permutationsprobleme. n = 20: mehr Operationen, als Atome im Universum.

Best Case, Worst Case, Average Case

Die Laufzeit eines Algorithmus kann je nach Eingabe variieren:

• Best Case: günstigste Eingabe (z. B. gesuchtes Element ist das erste).
• Worst Case: ungünstigste Eingabe — das ist meistens das Wichtigste.
• Average Case: durchschnittliche Eingabe (mathematisch komplizierter zu bestimmen).

Quicksort: Best Case O(n log n), Worst Case O(n²) (bei bereits sortierter Liste + ungünstiger Pivot), Average O(n log n).

Für Garantien interessiert der Worst Case — ein System darf nicht zufällig langsam werden.

Die Klassen P und NP

Hier wird es fundamental.

Klasse P (Polynomial): Alle Entscheidungsprobleme, die sich in polynomialer Zeit lösen lassen: O(n^k) für irgendeinen festen k. Zu P gehören: Sortieren, Suchen, kürzeste Wege, Matrizenmultiplikation, viele Optimierungsprobleme.

Polynomial wächst zwar, aber handhabbar — für realistische n.

Klasse NP (Nondeterministic Polynomial): Alle Entscheidungsprobleme, bei denen eine mögliche Lösung in polynomialer Zeit überprüft werden kann — auch wenn das Finden der Lösung exponentiell dauert.

Beispiel: Sudoku. Ein ausgefülltes Sudoku in polynomialer Zeit prüfen? Einfach. Alle Möglichkeiten durchprobieren, um es zu lösen? Exponentiell.

NP-vollständige Probleme

Manche Probleme in NP sind besonders schwer — sie gelten als NP-vollständig. Das bedeutet: Wenn man für dieses Problem eine polynomial-schnelle Lösung findet, kann man alle NP-Probleme polynomial lösen.

Travelling Salesman Problem (TSP): Ein Handelsreisender soll n Städte besuchen und dabei die kürzeste Route finden. Jede einzelne Route kann schnell berechnet werden — aber es gibt n! mögliche Routen. Bei 20 Städten: 2,4 Quintillionen Möglichkeiten. Kein bekannter Algorithmus schafft das besser als exponentiell.

Weitere NP-vollständige Probleme:

• Rucksackproblem (Welche Gegenstände maximieren den Wert bei begrenztem Gewicht?)
• Graphfärbung (Mit k Farben einfärben, sodass keine Nachbarn gleich gefärbt sind)
• Erfüllbarkeitsproblem (SAT: Gibt es eine Belegung, die eine logische Formel wahr macht?)

P = NP?

Die Kernfrage: Ist P = NP?

Wenn P = NP wäre, könnte man alle Probleme, deren Lösung schnell überprüft werden kann, auch schnell lösen. Das würde bedeuten: Kryptographie wäre wertlos (da viele Kryptosysteme auf der Schwere von NP-Problemen basieren). Optimierungsprobleme wären plötzlich effizient lösbar.

Fast alle Informatiker glauben, dass P ≠ NP — aber ein Beweis fehlt. Das ist eines der Millennium-Probleme des Clay Mathematics Institute, dotiert mit 1 Million Dollar.

Das Halteproblem: Die Grenze des Berechenbaren

Alan Turing bewies 1936, dass es Probleme gibt, die von keinem Algorithmus gelöst werden können — egal wie viel Zeit.

Das Halteproblem: Gibt es einen Algorithmus H, der für jedes beliebige Programm P und jede Eingabe I entscheidet, ob P(I) terminiert (also anhält) oder unendlich läuft?

Turings Beweis: Nein. Er konstruierte ein Paradox: Angenommen, H existiert. Dann baue ein Programm D, das H nutzt und bei jedem Input, bei dem H „hält” sagt, eine Endlosschleife einschlägt — und bei „läuft ewig” sofort hält. Was passiert, wenn man D mit sich selbst aufruft? Widerspruch.

Das Halteproblem ist unentscheidbar — es gibt kein Programm, das es allgemein löst. Das ist eine fundamentale Grenze aller Computer, nicht nur eine technische Einschränkung.

Praktisch: Viele verwandte Probleme (z. B. „Hat dieses Programm einen Fehler?”) sind ebenfalls unentscheidbar. Das ist der Grund, warum statische Analyse und Compiler nie alle Fehler finden können.

Beispiel aus dem Alltag

Kryptographie (P ≠ NP):

Passwörter und Transaktionen im Internet sind durch Kryptosysteme gesichert (RSA, AES). Viele davon basieren darauf, dass bestimmte Probleme schwer sind: Ein sehr großes Produkt zweier Primzahlen lässt sich leicht berechnen, aber die Primfaktorzerlegung eines großen Produkts ist extrem aufwändig. Wäre P = NP bewiesen, könnten solche Systeme in polynomialer Zeit geknackt werden.

Tourenplanung in Logistik:

Ein Lieferdienst optimiert Routen für Tausende von Lieferpunkten. Das ist im Kern ein TSP — NP-schwer. In der Praxis nutzt man deshalb keine exakten Lösungen, sondern gute Näherungsalgorithmen (Approximations-algorithmen, Heuristiken), die nicht optimal aber schnell genug sind.

Anwendung

Welche Komplexitätsklasse hat der Algorithmus in den folgenden Fällen (O-Notation)?

1. Finde das Maximum in einer unsortierten Liste.
2. Prüfe, ob ein Wort in einem Wörterbuch (als HashMap) steht.
3. Sortiere eine Liste mit Mergesort.
4. Zähle alle möglichen Sitzordnungen von 10 Personen.
5. Durchsuche eine sortierte Liste nach einem Element.

Ordne außerdem diese Komplexitäten von schnellstem zu langsamstem Wachstum: O(n²), O(log n), O(n!), O(n), O(2^n), O(1), O(n log n).

Typische Fehler

O-Notation mit exakter Laufzeit verwechseln: O(n log n) sagt nicht, wie viele Sekunden ein Algorithmus braucht — nur wie der Aufwand mit n wächst. Konstante Faktoren und Hardware sind andere Fragen.

NP mit „nicht lösbar” verwechseln: NP-Probleme sind lösbar — nur nicht bekanntermaßen in polynomialer Zeit. Für viele gibt es gute Näherungslösungen.

Best Case mit Durchschnitt gleichsetzen: Quicksort ist im Best Case O(n log n), aber mit einer schlecht gewählten Pivot-Strategie auf sortierten Listen O(n²). Das ist der Worst Case, den man kennen muss.

Das Halteproblem als Rechengrenze missverstehen: Das Halteproblem ist nicht ungelöst, weil Computer zu langsam sind — sondern weil Turing beweist, dass kein Algorithmus existieren kann. Es ist unentscheidbar, nicht nur schwer.

Zusammenfassung

• O-Notation beschreibt das Wachstum des Rechenaufwands mit n: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)
• Klasse P: Probleme, die in polynomialer Zeit gelöst werden können
• Klasse NP: Probleme, deren Lösungen in polynomialer Zeit überprüft werden können
• NP-vollständige Probleme (TSP, Rucksack, SAT) sind die schwersten in NP — ein Durchbruch hier würde alle NP-Probleme lösen
• P = NP? ist das größte offene Problem der Informatik — fast alle glauben P ≠ NP
• Das Halteproblem (Turing) zeigt, dass manche Probleme prinzipiell unentscheidbar sind — eine fundamentale Grenze aller Berechnungen

Quiz

Frage 1: Erkläre den Unterschied zwischen O(n) und O(n²) — und was passiert, wenn n von 1.000 auf 10.000 steigt?

Frage 2: Was ist der Unterschied zwischen P und NP?

Frage 3: Was ist das Travelling Salesman Problem — und warum ist es NP-vollständig?

Frage 4: Was hat Turing mit dem Halteproblem bewiesen — und was bedeutet das in der Praxis?