E (Komplexitätsklasse)
Sign in to saveBegriff aus der Informatik
Wikidata facts
- Instance of
- complexity class
- Part of
- EXPTIME
- Has part
- PSPACE
Show 1 more fact
- different from
- E
Sources (1)
via Wikidata · CC0
Article · Deutsch
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.
Abstract from DBpedia / Wikipedia · CC BY-SA