E (Komplexitätsklasse)

Die Komplexitätsklasse $𝐄$ 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 𝐄$ 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 $𝐄$ spielt in der Komplexitätstheorie eine wichtige Rolle, da sie nicht wie EXPTIME unter Polynomialzeitreduktion abgeschlossen ist. Denn damit kann man schließen: PSPACE$=𝐄$. Während für $𝐄𝐗𝐏𝐓𝐈𝐌𝐄$ bekannt ist: $𝐏𝐒𝐏𝐀𝐂𝐄\subseteq 𝐄𝐗𝐏𝐓𝐈𝐌𝐄$, ist für $𝐄$ keine Relation zu $𝐏𝐒𝐏𝐀𝐂𝐄$ bekannt.

Weblinks

• Vorlage:Complexity Zoo