E (Komplexitätsklasse)

Die Komplexitätsklasse ${\displaystyle \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 ${\displaystyle L\in \mathbf {E} }$ eine Turingmaschine ${\displaystyle M_{L}}$ mit einer Zeitschranke ${\displaystyle t_{L}(n)\in O(k^{n})}$ für ein beliebiges ${\displaystyle k\in \mathbb {N} }$, so dass für alle ${\displaystyle w\in L}$ die Maschine ${\displaystyle M_{L}}$ das Wort ${\displaystyle w}$ in höchstens ${\displaystyle t_{L}(|w|)}$ Schritten akzeptiert.

Die Klasse ${\displaystyle \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${\displaystyle \not =\mathbf {E} }$. Während für ${\displaystyle \mathbf {EXPTIME} }$ bekannt ist: ${\displaystyle \mathbf {PSPACE} \subseteq \mathbf {EXPTIME} }$, ist für ${\displaystyle \mathbf {E} }$ keine Relation zu ${\displaystyle \mathbf {PSPACE} }$ bekannt.

Weblinks

• E. In: Complexity Zoo. (englisch)