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)