Exponential Time Hypothesis

Manche Rechenprobleme scheinen egal wie klug man vorgeht immer sehr lange zu dauern. Die Exponential Time Hypothesis, kurz ETH, ist eine Vermutung aus der Theoretischen Informatik — dem Teilgebiet, das untersucht, was Computer grundsätzlich leisten können und was nicht. Sie behauptet: Für eine bestimmte Klasse von Problemen gibt es keinen Algorithmus, der wesentlich schneller als exponentiell ist. Ein exponentiell laufender Algorithmus verdoppelt seine Rechenzeit, wenn man das Problem nur um einen einzigen Schritt vergrößert. Bei zwanzig Variablen braucht er schon über eine Million Schritte; bei sechzig Variablen wäre selbst der schnellste Supercomputer überfordert. Die ETH sagt: Daran lässt sich im Kern nichts ändern.

Die ETH als Maßstab für Algorithmen

Ohne die ETH könnte man immer noch hoffen: Vielleicht findet jemand morgen einen genialen Trick, der ein schweres Problem plötzlich schnell lösbar macht. Die ETH schränkt diese Hoffnung systematisch ein. Sie liefert ein theoretisches Fundament, auf dem Informatiker beweisen können: Falls die ETH stimmt, dann kann kein Algorithmus für Problem X schneller als Y sein.

Das ist praktisch wichtig, weil es Forschungszeit spart. Wer weiß, dass eine schnellere Lösung unter der ETH unmöglich wäre, muss nicht weitersuchen. Stattdessen kann man gezielt nach guten Näherungslösungen suchen, die das Problem nicht perfekt, aber schnell genug lösen. Die ETH verschiebt also den Fokus von „Gibt es eine perfekte Lösung?“ zu „Was ist das Beste, das wir realistisch erreichen können?“

Wichtig ist: Die ETH ist bis heute nicht bewiesen. Sie ist eine Vermutung, wenn auch eine, an die nahezu alle Fachleute glauben. Viele Resultate in der Algorithmik hängen davon ab — ähnlich wie ein Kartenhaus, das stabil steht, solange die unterste Karte hält.

Das Kernproblem hinter der Hypothese

Die ETH bezieht sich ursprünglich auf ein konkretes Problem namens SAT — kurz für Erfüllbarkeitsproblem. Dabei geht es um logische Aussagen mit vielen Variablen, die entweder wahr oder falsch sein können. Die Frage lautet: Gibt es eine Belegung der Variablen, die die gesamte Aussage erfüllt? Man kann das als riesiges Rätsel vorstellen, bei dem man viele Schalter umlegen muss, um eine Lampe zum Leuchten zu bringen — und es gibt kein Schema, das einem sagt, in welcher Reihenfolge man anfangen soll.

Die ETH behauptet: Für SAT braucht jeder Algorithmus im schlechtesten Fall Zeit, die mit der Anzahl der Variablen exponentiell wächst. Eine stärkere Variante, die Strong Exponential Time Hypothesis (SETH), verschärft dies weiter. Sie sagt, dass nicht einmal geringfügige Verbesserungen an der exponentiellen Laufzeit möglich sind. Aus SETH lassen sich noch engere Schranken für viele andere Probleme ableiten.

Der entscheidende Gedankengang dahinter ist folgender: Wenn man zeigen kann, dass ein Problem mindestens so schwer ist wie SAT, dann gelten für dieses Problem dieselben Grenzen. Dieses Übertragen von Schwierigkeit nennt man Reduktion — ein zentrales Werkzeug in der Theoretischen Informatik.

Wo die ETH in der Praxis auftaucht

Die ETH taucht überall dort auf, wo Informatiker begründen wollen, warum ein Problem schwer ist und bleibt. In der Datenbankforschung etwa nutzt man ETH-basierte Argumente, um zu zeigen, dass bestimmte Abfragen über große Datenmengen nicht wesentlich schneller beantwortet werden können, als es aktuelle Systeme bereits tun. In der Netzwerkanalyse begründet sie, warum manche Optimierungsprobleme auf großen Graphen — Strukturen aus Punkten und Verbindungen — nicht effizient lösbar sind.

Auch in der KI-Forschung spielt sie eine Rolle. Viele Planungs- und Suchprobleme, die KI-Systeme lösen sollen, sind eng mit SAT verwandt. Die ETH hilft dabei, realistische Erwartungen zu setzen: Nicht jedes Problem, das ein Mensch intuitiv lösen kann, lässt sich auch effizient automatisieren.

In den Nachrichten taucht die ETH seltener direkt auf — öfter steckt sie hinter Schlagzeilen wie „Quantencomputer löst Problem, das klassische Rechner nicht schaffen“. Solche Behauptungen lassen sich erst einordnen, wenn man weiß, was die ETH über die Grenzen klassischer Algorithmen aussagt. Sie ist also weniger ein Alltagsbegriff als ein Schlüsselkonzept, das im Hintergrund viele Diskussionen über Rechnerleistung und KI-Fähigkeiten strukturiert.