E (Komplexitätsklasse)
Die Komplexitätsklasse <math>\mathbf E</math> 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 <math>L\in\mathbf E</math> eine Turingmaschine <math>M_L</math> mit einer Zeitschranke <math>t_L(n)\in O(k^n)</math> für ein beliebiges <math>k\in\mathbb N</math>, so dass für alle <math>w\in L</math> die Maschine <math>M_L</math> das Wort <math>w</math> in höchstens <math>t_L(|w|)</math> Schritten akzeptiert.
Die Klasse <math>\mathbf E</math> spielt in der Komplexitätstheorie eine wichtige Rolle, da sie nicht wie EXPTIME unter Polynomialzeitreduktion abgeschlossen ist. Denn damit kann man schließen: PSPACE<math>\not= \mathbf E</math>. Während für <math>\mathbf{EXPTIME}</math> bekannt ist: <math>\mathbf{PSPACE}\subseteq\mathbf{EXPTIME}</math>, ist für <math>\mathbf E</math> keine Relation zu <math>\mathbf{PSPACE}</math> bekannt.
Weblinks
- E. In: Complexity Zoo. (englisch)