Gleichheit von Nspace- und Konspace -Klassen

Question

Ich versuche zu entscheiden, welche der folgenden Aussagen wahr sind:

1. $ mathsf {nspace} ( log log n) = mathsf {conspace} ( log log n) $

2. $ mathsf {nspace} ( lg^2n) = mathsf {conspace} ( lg^2n) $

3. $ mathsf {nspace} ( sqrt n) = mathsf {conspace} ( sqrt n) $

Ich dachte sofort, dass (1) korrekt ist, da $ lg lg n < lg n $ und da $ mathsf {nl} = mathsf {conl} $, dachte ich, dass die Aussage daraus ergibt. Ich dachte, da wir nicht wissen, ob $ mathsf {p} = mathsf {pspace} $, können wir nichts über eine Klasse sagen, die größer als $ lg n $ und eine Teilmenge von $ p $ ist.

Aber es ist genau das Gegenteil. (1) ist nicht unbedingt wahr, während (2) und (3) notwendigerweise wahr sind. Warum ist das so?

Die Frage stammt aus der vergangenen Zwischenzeit, die ich jetzt löste.

Answer 1

Ich kann mir momentan kein Gegenbeispiel für (i) vorstellen. Aber (ii) und (iii) sind aufgrund des Imerman-Szelepcsényi-Satzes [1] zutreffend, nach dem $ text {nspace} (s (n)) = text {co-nspace} (s (n)) $ für alle $ s (n) geq log (n) $.

[1]: Wikipedia - Immerman -Szelepcsényi Theorem