E (Komplexitätsklasse)

Die Komplexitätsklasse $\mathbf {E}$ ist die Klasse aller Sprachen, die sich von einer deterministischen Turingmaschine in exponentieller Zeit mit linearem Exponenten lösen lassen. Es existiert also für jedes $L\in \mathbf {E}$ eine Turingmaschine $M_{L}$ mit einer Zeitschranke $t_{L}(n)\in O(k^{n})$ für ein beliebiges $k\in \mathbb {N}$, so dass für alle $w\in L$ die Maschine $M_{L}$ das Wort $w$ in höchstens $t_{L}(|w|)$ Schritten akzeptiert.

Die Klasse $\mathbf {E}$ spielt in der Komplexitätstheorie eine wichtige Rolle, da sie nicht wie EXPTIME unter Polynomialzeitreduktion abgeschlossen ist. Denn damit kann man schließen: PSPACE$\not =\mathbf {E}$. Während für $\mathbf {EXPTIME}$ bekannt ist: $\mathbf {PSPACE} \subseteq \mathbf {EXPTIME}$, ist für $\mathbf {E}$ keine Relation zu $\mathbf {PSPACE}$ bekannt.

Weblinks

• E. In: Complexity Zoo. (englisch)