← Glossar Begriff
Exponential Time Hypothesis
Eine weit verbreitete Annahme in der Informatik, dass manche schwierigen Logikrätsel im schlimmsten Fall nicht schnell gelöst werden können.
Der Exponential Time Hypothesis besagt, dass es für eine berühmte Art von Rätsel namens SAT (Werte finden, die eine logische Aussage wahr machen) keine clevere Abkürzung gibt. Im schlimmsten Fall verdoppelt sich der Zeitaufwand mit jeder zusätzlichen Variable ungefähr, was sehr schnell unmöglich wird.
Niemand hat es bewiesen, aber Hunderte von Forschungsarbeiten gehen davon aus, dass es wahr ist, und bauen darauf auf. Wenn jemand es wirklich widerlegen würde, würden diese Papiere ihre Grundlage verlieren, auch wenn ihre Ergebnisse immer noch richtig sein könnten.
Erwähnt in