Ist $ mathsf {nspace} (f (n)) = mathsf {conspace} (f (n)) $ $ für $ f (n) < log (n) $?

Question

Es ist bekannt, dass für $ f (n) Geq log n $, $ mathsf {nspace} (f (n)) = mathsf {conspace} (f (n)) $.

Was ist, wenn $ f (n) < log n $? Sind sie auch gleich?

Answer 1

Imerman - Szelepcsényi Theorem arbeitet unter logarithmischen Reduktionen. Unterlogarithmische Weltraumklassen haben unterschiedliche Reduktionen. Die TMs arbeiten innerhalb Der Unterlogarithmische Raum kann nicht einmal die Länge des Eingangs aufzeichnen. Es wurde gezeigt, dass die Raumhierarchie für jeden untergebundenen Subllogarithmic Ω (log log n)- o (log n) ist unendlich. Sie finden es in folgenden Referenzen:

V. Geffert. Der Unterlogarithmische σ2-Raum wird nicht unter Komplement und anderen Trennungsergebnissen geschlossen. Theoretische Informatik und Anwendungen, 27: 349–366, 1993.

M. Liśkiewicz und R. Reischuk. Trennung der niedrigeren Ebenen der Unterlogarithmischen Raumhierarchie. In Proceedings of the Symposium über theoretische Aspekte der Informatik, Seiten 6–27, 1993.

B. von Braunmuhl "Wechsel für Zwei-Wege-Maschinen mit Unterlogarithmischer Raum"In Proceedings of the Symposium über theoretische Aspekte der Informatik, Seiten 5–15, 1993.

Das Papier Die Komplexitätswelt unter dem logarithmischen Raum Von M. Liśkiewicz und Reischuk enthält eine hervorragende Abwicklung des Unterlogarithmischen Raums.