Exponentielle Hierarchie

Im Computerkomplexitätstheorie, das Exponentielle Hierarchie ist eine Hierarchie von Komplexitätsklassen, was ist ein Exponentialzeit Analogon der Polynomhierarchie. Wie anderswo in der Komplexitätstheorie wird „exponentiell“ in zwei verschiedenen Bedeutungen verwendet (lineare Exponentialgrenzen für eine Konstante c, und volle exponentielle Grenzen ), was zu zwei Versionen der exponentiellen Hierarchie führt.[1][2] Diese Hierarchie wird manchmal auch als die bezeichnet schwach exponentielle Hierarchie, um sie von der zu unterscheiden stark Exponentielle Hierarchie.[2][3]

Eh

EH ist die Vereinigung der Klassen für alle k, wo (d. H. Sprachen berechnet in Nichtdeterministisch Zeit für einige Konstante c mit einer Orakel). Man definiert auch

Eine äquivalente Definition ist, dass eine Sprache L ist in Wenn und nur wenn es in der Form geschrieben werden kann

wo ist ein Prädikat, das rechtzeitig berechnet wird (was implizit die Länge von begrenzt yi). Auch gleichwertig ist EH die Klasse von Sprachen, die auf einem berechnet werden können Wechsel Turing Machine rechtzeitig für einige c mit ständig vielen Wechseln.

Exph

Exph ist die Vereinigung der Klassen , wo (Sprachen, die in nicht deterministischer Zeit berechnet werden können für einige Konstante c mit einer Orakel) und wieder:

Eine Sprache L ist in Wenn und nur wenn es als geschrieben werden kann

wo ist rechtzeitig berechnet für einige c, was wieder implizit die Länge von angrenzt yi. Equivalent ist Exph die Klasse von Sprachen, die rechtzeitig berechnet werden können auf einer abwechselnden Turing -Maschine mit ständig vielen Wechseln.

Vergleich

ENe ⊆ Eh⊆ Espace,
ExpNexp ⊆ exph⊆ Expace,
Eh ⊆ exph.

Verweise

  1. ^ Sarah Mocas, die Klassen in der Exponential-Zeit-Hierarchie von Klassen in trennen PH, Theoretische Informatik 158 (1996), Nr. 1–2, S. 221–231.
  2. ^ a b Anuj Dawar, Georg Gottlob, Lauri Hella, erfassen relativierte Komplexitätsklassen ohne Ordnung, mathematische Logik Quarterly 44 (1998), Nr. 1, S. 109–122.
  3. ^ Hemachandra, Lane A. (1989). "Die starke exponentielle Hierarchie bricht zusammen". Journal of Computer and System Sciences. 39 (3): 299–322.

Externe Links

Komplexitätszoo: Klasse EH