E (Komplexitätsklasse)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

  • E. In: Complexity Zoo. (englisch)