Das Kefk Network Wiki befindet sich im Testbetrieb.

E (Komplexitätsklasse)

Aus Kefk.

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.