Next: Alternierung Up: Generalisierte Berechnungen in Iterativen Previous: Trade-off-Sätze

Hierarchiesätze

Die Hierarchiesätze haben die Form, daß zwei der drei Größen (Raum, Zeit, Nichtdeterminismus) festgehalten werden. Es wird dann folgende Frage untersucht: ,,Wie muß die dritte Größe geändert werden, um eine echte Inklusion zu erhalten¿` Ergebnisse:

Es gibt eine dichte Hierarchie über die Anzahl der Nichtdeterministischen Schritte (Satz 5.1).
Bei deterministischen iterativen Arrays befindet sich zwischen Real- und Linearzeit eine dichte Zeithierarchie (Satz 5.9). Zusammen mit dem bereits bekannten Satz 5.10 ist damit die Frage nach Zeithierarchien bei iterativen Arrays nach mehr als 30 Jahren geklärt.
Der Zeithierarchiesatz läßt sich nur eingeschränkt auf nichtdeterministische iterative Arrays übertragen (Satz 5.11). Bei kleinen Zeitschranken existiert eine Komplexitätslücke (Satz 5.7). (Im Extremfall des unbeschränkten Nichtdeterminismus gilt $\mathscr{L}_{rt}(\operatorname{NIA})=\mathscr{L}_{lt}(\operatorname{NIA})$ .)
Es gibt eine Hierarchie über die Speicherdimension (Satz 5.13).

Andreas Klein
2000-01-11