Inhalt
E (Komplexitätsklasse)
E (Komplexitätsklasse)
Die Komplexitätsklasse 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 
eine Turingmaschine ML
mit einer Zeitschranke
für ein beliebiges
, so dass für alle
die Maschine ML
das Wort w in höchstens tL
( | w | ) Schritten akzeptiert.
Die Klasse 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. Während für EXPTIME bekannt ist:
, ist für E keine Relation zu PSPACE bekannt.
Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel E (Komplexitätsklasse) aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren