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 eine Turingmaschine mit einer Zeitschranke für ein beliebiges , so dass für alle die Maschine das Wort in höchstens 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: , ist für keine Relation zu bekannt.
Weblinks Bearbeiten
- E. In: Complexity Zoo. (englisch)