Exponentialzeit-Hypothese

Einfache Sprache

Die Exponentialzeit-Hypothese besagt das 3SAT nicht in sub-exponential time $2^{\mathcal o(n)}$.

Satz Exponential Time Hypothesis

Es existiert eine positive Zahl $\delta\in\mathbb R$ so, dass 3SAT mit $n$ Variablen und $m$ Klauseln nicht in Zeit $2^{\delta n}(n+m)^{\mathcal O(1)}$ gelöst werden kann.

• Vorlesungsansatzt aus der script nehmen mit sparsifivation lemma und einfache Sprache ändern