Exponentialzeithypothese (ETH)

Manche Aufgaben können wir nur lösen, indem wir fast alle Möglichkeiten ausprobieren. Die Exponentialzeithypothese, englisch Exponential Time Hypothesis und kurz ETH, ist die Wette von Informatikern, dass es bei einer ganz bestimmten Aufgabe nicht anders geht, so clever wir auch sein mögen. Schnellere Verfahren gibt es zwar, aber selbst die besten brauchen eine Anzahl von Schritten, die mit der Größe der Aufgabe exponentiell wächst.

Die ETH hängt eng mit dem Problem P versus NP zusammen, dem wir einen eigenen Artikel gewidmet haben. Wenn du ihn noch nicht gelesen hast, wirf zuerst einen Blick hinein, wir bauen darauf auf. Vor allem darauf, was die Komplexität eines Algorithmus ist und warum zwischen n² und 2ⁿ so ein riesiger Abgrund liegt.

Wen zur Feier einladen

Du planst eine Feier und willst vier Freunde einladen: Thomas, Jan, Katrin und Daniel. Der Haken: Zwischen ihnen herrschen unterschiedliche Beziehungen, und du möchtest, dass alle zufrieden sind. Nach langem Nachfragen kommst du auf sechs Bedingungen:

1. Thomas oder Katrin kommt (gern auch beide).
2. Jan und Katrin können sich nicht leiden, also kommen nicht beide.
3. Daniel kommt nur dann, wenn auch Jan kommt.
4. Wenn Thomas kommt, muss auch Katrin oder Daniel kommen.
5. Wenn Thomas und Katrin kommen, muss auch Jan kommen.
6. Mindestens einer aus dem Trio Thomas, Jan, Daniel kommt.

Wen musst du einladen, damit alle Bedingungen gleichzeitig erfüllt sind? Versuche es zuerst selbst, die Lösung verraten wir am Ende des Artikels.

Informatiker würden die Aufgabe in die Sprache der Aussagenlogik übersetzen. Jeder Freund bekommt einen Buchstaben, zum Beispiel T für Thomas. Der Buchstabe ist entweder wahr (Thomas kommt) oder falsch (Thomas kommt nicht). Das Symbol ∨ lesen wir „oder“ und ¬ lesen wir „nicht“. Die erste Bedingung sieht dann so aus:

$$T\vee K$$

Die zweite Bedingung sagt, dass Jan nicht kommt oder Katrin nicht kommt:

$$\mathrm{\neg }J\vee \mathrm{\neg }K$$

Bei der dritten Bedingung verheddert man sich leicht. „Daniel kommt nur dann, wenn auch Jan kommt“ bedeutet, dass es nicht passieren darf, dass Daniel kommt und Jan nicht. Also kommt entweder Daniel nicht oder Jan kommt:

$$\mathrm{\neg }D\vee J$$

Auf die gleiche Weise schreiben wir auch den Rest um. Die ganze Aufgabe sieht dann so aus:

$$\begin{array}{rcl}1.& & T\vee K\\ 2.& & \mathrm{\neg }J\vee \mathrm{\neg }K\\ 3.& & \mathrm{\neg }D\vee J\\ 4.& & \mathrm{\neg }T\vee K\vee D\\ 5.& & \mathrm{\neg }T\vee \mathrm{\neg }K\vee J\\ 6.& & T\vee J\vee D\end{array}$$

Sieh dir an, wie ähnlich sich die Bedingungen sind: ein paar Buchstaben, manche mit dem Zeichen ¬, verbunden durch das Wort „oder“. Und keine davon hat mehr als drei Buchstaben. Eine Aufgabe, in der wir solche Bedingungen haben und den Buchstaben Wahr und Falsch so zuordnen sollen, dass alle Bedingungen gleichzeitig gelten, heißt 3-SAT. Die Drei bedeutet, dass eine Bedingung höchstens drei Buchstaben hat, und SAT ist die Abkürzung des englischen satisfiability, Erfüllbarkeit.

Auf den ersten Blick ist das eine Spielerei für die Rätselecke. Aber in die Form 3-SAT lässt sich eine riesige Menge praktischer Aufgaben umschreiben: Stundenpläne, die Prüfung, dass ein Chip im Prozessor richtig rechnet, die Schichtplanung und auch Sudoku. Dann gibt es nicht vier Buchstaben, sondern gern Millionen.

Wie viele Möglichkeiten müssen wir ausprobieren?

Das direkteste Vorgehen ist, alles auszuprobieren. Thomas kommt oder kommt nicht, das sind zwei Möglichkeiten. Bei jeder davon kommt Jan, oder er kommt nicht, das sind schon vier Möglichkeiten. Bei vier Freunden sind es

$$2\cdot 2\cdot 2\cdot 2=2^4=16.$$

Genauso haben wir bei den Binärvektoren im Artikel zu P versus NP überlegt. Haben wir n Buchstaben, können wir ihnen auf 2ⁿ Arten Wahr und Falsch zuordnen. Bei 4 Freunden sind das 16 Möglichkeiten, die du in ein paar Minuten durchgehst. Bei 100 Buchstaben sind es

$$2^{100}\approx 1,27\cdot {10}^{30}$$

Möglichkeiten. Würde ein Computer eine Milliarde Möglichkeiten pro Sekunde prüfen, bräuchte er dafür ungefähr dreitausendmal so viel Zeit, wie das Universum alt ist.

Umgekehrt ist es aber leicht: Wenn dir jemand sagt „lade diese drei ein“, prüfst du es sofort. Du musst nur die sechs Bedingungen durchgehen und bei jeder nachsehen, ob sie gilt. Eine Lösung zu finden ist schwer, sie zu überprüfen ist leicht. Genau solche Aufgaben haben wir im Artikel zu P versus NP in die Klasse NP eingeordnet.

Aber 3-SAT ist in NP keine beliebige Aufgabe: 1971 wurde gezeigt, dass sich jede Aufgabe aus NP in 3-SAT übersetzen lässt. Wer also 3-SAT schnell lösen könnte, könnte schnell alles lösen, was sich schnell überprüfen lässt. Aufgaben mit dieser Eigenschaft heißen NP-vollständig, und 3-SAT ist ihr berühmtester Vertreter.

Geht es schneller als 2ⁿ?

Ja. Alles auszuprobieren ist gar nicht nötig. Es genügt zum Beispiel zu bemerken, dass Thomas nicht kommt: Aus der ersten Bedingung folgt dann sofort, dass Katrin kommen muss. Alle Möglichkeiten, in denen keiner von beiden kommt, streichen wir gleich. Clevere Algorithmen kombinieren eine ganze Reihe solcher Tricks. Die besten heute bekannten brauchen ungefähr

$${\mathrm{1,307}}^n$$

Schritte. Das ist ein gewaltiger Sprung. Für n = 100 kommen statt 10³⁰ ungefähr 4,2 · 10¹¹ Schritte heraus, was ein Computer in ein paar Minuten schafft.

Aber Vorsicht, der Haken. 1,307ⁿ ist immer noch eine Exponentialfunktion. Wir haben die Basis von zwei auf 1,307 verkleinert, aber die Variable n steht weiterhin im Exponenten. Wenn n weiter wächst, überrollt es uns am Ende trotzdem. Für n = 1000 ist selbst 1,307ⁿ eine Zahl mit 117 Ziffern.

Und wie würde ein Algorithmus aussehen, der nicht exponentiell ist? Zum Beispiel einer, der mit n³ Schritten auskommt. Er wäre polynomiell, und 3-SAT läge dann in der Klasse P. Zwischen Polynomen und Exponentialfunktionen liegt aber noch eine Grauzone: Funktionen, die schneller wachsen als jedes Polynom und trotzdem langsamer als jede Exponentialfunktion. Zum Beispiel

$$2^{\sqrt{n}}.$$

Hier steht im Exponenten nur die Wurzel aus n. Vergleichen wir alle vier Funktionen in einer Tabelle:

Für n = 1000 spielt $2^{\sqrt{n}}$ in derselben Liga wie n³, während beide Exponentialfunktionen in Zahlen davongelaufen sind, für die wir nicht einmal Namen haben. Funktionen wie $2^{\sqrt{n}}$, die für jede Basis c größer als eins langsamer wachsen als cⁿ, nennt man subexponentiell.

Dasselbe zeigt der Graph. Die senkrechte Achse ist logarithmisch: Jeder Teilstrich nach oben bedeutet eine hunderttausendmal größere Zahl. Sonst würde außer 2ⁿ nichts ins Bild passen.

Exponentialfunktionen sind in so einem Graphen Geraden, die ständig ansteigen. Die rote 2ⁿ ist steiler als die orange 1,307ⁿ, aber beide sind Geraden. Interessant ist, dass die orange anfangs sogar unter der grünen n³ liegt. Sie überholt diese erst bei etwa n = 42, dann aber für immer. Die blaue $2^{\sqrt{n}}$ biegt sich dagegen und bleibt unten bei der grünen.

Was die ETH genau behauptet

Jetzt können wir die Hypothese aussprechen. 1999 haben sie Russell Impagliazzo und Ramamohan Paturi formuliert:

Es gibt eine Zahl c größer als eins, sodass kein Algorithmus 3-SAT mit n Buchstaben schneller als in ungefähr cⁿ Schritten lösen kann.

Und in normaler Sprache? Die Basis der Exponentialfunktion können wir mit cleveren Tricks verkleinern, von zwei auf 1,5, auf 1,307, vielleicht einmal auf 1,2. Aber wir drücken sie nie beliebig nah an die Eins. Irgendwo liegt eine Grenze, unter die es nicht geht. Einen Algorithmus mit der Komplexität $2^{\sqrt{n}}$ dürfte es nach der ETH also nicht geben.

Warum Hypothese? Weil es niemand beweisen kann. Die ETH ist eine Arbeitsannahme, ähnlich wie wir im Artikel zu P versus NP annehmen, dass P ≠ NP gilt. Die meisten Informatiker glauben daran, weil Jahrzehnte des Bemühens nur gebracht haben, dass sich die Basis langsam von zwei nach unten schiebt. Einen Beweis hat aber niemand in der Hand.

ETH und P versus NP

Wie hängen diese beiden Fragen zusammen? Stell dir vor, 3-SAT hat eine „wahre“ Schwierigkeit, nämlich den schnellstmöglichen Algorithmus. Der kann in drei Bereichen liegen:

• Grüner Bereich, polynomiell. 3-SAT lässt sich zum Beispiel in n³ Schritten lösen. Da 3-SAT NP-vollständig ist, würde dann P = NP gelten, und die ETH wäre natürlich falsch.
• Blauer Bereich, subexponentiell. 3-SAT lässt sich in $2^{\sqrt{n}}$ Schritten oder etwas Ähnlichem lösen. Polynomiell nicht, also gilt P ≠ NP. Aber die ETH wäre falsch.
• Roter Bereich, exponentiell. Besser als cⁿ geht es nicht. Die ETH gilt, und damit gilt auch P ≠ NP.

Am Bild sieht man, dass die ETH eine stärkere Aussage ist als P ≠ NP. Sie sagt nicht nur, dass sich 3-SAT nicht polynomiell lösen lässt, sondern auch nicht subexponentiell. Wer die ETH beweisen würde, würde damit auch P ≠ NP beweisen und eine Million Dollar bekommen.

Und umgekehrt: Wer die ETH widerlegen würde, hätte damit noch nicht P = NP bewiesen. Ihm genügt ein Algorithmus aus dem blauen Bereich. Merk dir das, wir brauchen es gleich.

Wozu die ETH gut ist

Zu beweisen, dass sich eine Aufgabe nicht schnell lösen lässt, ist in der Informatik unglaublich schwer. Fast nichts dergleichen können wir. Die ETH gibt uns eine Hintertür: Statt „Aufgabe X ist schwer“ beweisen wir „Aufgabe X ist schwer, falls die ETH gilt“.

Wie? Wir zeigen, dass sich mit einer schnellen Lösung der Aufgabe X auch 3-SAT schnell lösen ließe. Nehmen wir zum Beispiel diese: Wir haben n Leute, und von manchen Paaren wissen wir, dass sie sich nicht leiden können. Wir wollen sie auf drei Räume so verteilen, dass kein solches Paar im selben Raum landet. Informatiker nennen das Färben eines Graphen mit drei Farben. Aus jeder 3-SAT-Aufgabe lässt sie sich so konstruieren, dass die Zahl der Leute nur ein Vielfaches der Zahl der Buchstaben ist. Ließen sich die Leute also subexponentiell auf die Räume verteilen, ließe sich auch 3-SAT subexponentiell lösen, und die ETH wäre gefallen.

Solche bedingten Ergebnisse gibt es heute Hunderte. Das ganze Gebiet, das untersucht, wie schwer einzelne Aufgaben genau sind, steht auf der ETH wie ein Haus auf seinem Fundament.

Die ETH hat auch eine stärkere Schwester, die starke Exponentialzeithypothese (SETH). Sie bezieht sich auf Aufgaben, in denen die Bedingungen mehr als drei Buchstaben haben dürfen, etwa zehn oder hundert. Die SETH behauptet: Je längere Bedingungen wir zulassen, desto näher kommt die beste mögliche Basis der Zwei. Bei langen Bedingungen ließe sich also fast nichts gegenüber dem dummen Ausprobieren aller 2ⁿ Möglichkeiten sparen.

Warum jetzt über die ETH gesprochen wird

Das Unternehmen OpenAI, das du vor allem durch ChatGPT kennst, hat im Oktober 2026 einen Preprint veröffentlicht, also einen Artikel, der noch nicht begutachtet wurde. Er heißt The Exponential Time Hypothesis is False, auf Deutsch „Die Exponentialzeithypothese ist falsch“. Darin behauptet OpenAI, einen Algorithmus gefunden zu haben, der 3-SAT in ungefähr

$$2^{\frac{n}{\sqrt{\ln n}}}$$

Schritten löst. Im Exponenten steht also nicht n allein, sondern n geteilt durch die Wurzel aus dem (natürlichen) Logarithmus. Dieser Nenner wächst furchtbar langsam, aber er wächst, und das genügt, damit die Funktion subexponentiell ist. Der Algorithmus soll sogar nicht nur eine Lösung finden, sondern auch zählen können, wie viele Lösungen es gibt.

Würde das stimmen, fiele der Algorithmus von OpenAI in den blauen Bereich aus dem Bild weiter oben. Und was würde das bedeuten?

• Die ETH würde fallen und mit ihr auch die SETH und Hunderte bedingte Ergebnisse, die auf ihnen standen. Die Informatiker müssten viele „falls die ETH gilt, dann …“ wegwerfen oder umschreiben.
• Das Problem P versus NP würde es nicht lösen. Der Algorithmus ist immer noch nicht polynomiell.
• In der Praxis würde sich fast nichts ändern. In der Formel stecken Konstanten, die wir nicht kennen. Wären sie gleich eins, ergäbe sich für n = 1000 etwa 2,6 für $\sqrt{\ln n}$, und wir bekämen ungefähr 2³⁸⁰ Schritte. Das ist fast dasselbe wie 1,307¹⁰⁰⁰ ≈ 2³⁸⁶ bei den besten heutigen Algorithmen. Die heutigen Algorithmen würde der neue erst für noch größere n deutlich überholen, und um wie viel, hängt gerade von den unbekannten Konstanten ab. Er hat also vor allem theoretische Bedeutung. Verschlüsselung und Bankwesen betrifft das nicht.

Bisher handelt es sich um eine ungeprüfte Behauptung. Der Beweis ist lang und technisch, und die Fachleute fangen erst an, ihn zu lesen. Große Ankündigungen gelöster Probleme haben sich in der Vergangenheit schon oft als fehlerhaft erwiesen, deshalb gilt vorerst: Wir warten ab, was die Fachleute dazu sagen. Diesen Absatz schreiben wir am 27. Oktober 2026.

Lösung der Aufgabe mit der Feier

Einladen sollst du Thomas, Jan und Daniel, Katrin nicht. Die Abbildung zeigt alle 16 Möglichkeiten. In jeder Spalte steht eine Möglichkeit: Ein ausgefüllter Kreis bedeutet, dass der Freund kommt, ein leerer, dass er nicht kommt. Die rote Zahl unter der Spalte zeigt die erste Bedingung, die nicht gilt. Die einzige Möglichkeit, bei der alle Bedingungen gelten, ist grün umrandet.

Und genau das ist die rohe Gewalt, die die ETH für fast unschlagbar hält: bei vier Freunden sechzehn Spalten, bei hundert Freunden mehr Spalten, als unser Körper Atome hat.

Siehe auch

• Das größte Problem der Informatik: P versus NP
• Aussagenlogik
• Exponentialfunktion
• Exponentielles Wachstum