Immerman Theorem NLogSpace = co-NLogSpace

Neue Frage »

Auf diesen Beitrag antworten »
tom Immerman Theorem NLogSpace = co-NLogSpace

Hi.

Ich versuche derzeit das Immerman Theorem nachzuvollziehen und habe schon diverse Texte und Algorithmen dazu angeschaut.

Ich erklär mal eben was ich dazu weiß, um dann meine Frage präziser stellen zu können.

Okay, also man will ja zeigen, dass ein Knoten in einem Graph nicht erreichbar ist, weil um zu zeigen dass ein Knoten erreichbar ist, benötigt man nur logarithmisch viel Platz. Wenn das in LogSpace möglich ist, dann hat man quasi gezeigt, dass NLogSpace = co-NLogSpace, weil nicht PATH NLogSpace-Vollständig ist.

In dem Algorithmus dazu rät man einen erreichbaren Knoten (man sagt quasi einfach, der ist erreichbar, aber man weiß es noch nicht.) Dann ermittelt man für diesen Knoten, ob dieser vom Startknoten s aus erreichbar ist. Das tut man so weit ich das verstanden habe, indem man überprüft, ob es einen Pfad der maximalen Länge (Distanz) i oder weniger zu diesem Knoten gibt.

Da würde ich jetzt denken, okay, dann fang ich mal bei dem Startknoten s an und nehme mir irgendeinen Nachbarknoten v von dem und merke mir, dass ich meine Distanz jetzt um 1 erhöht habe. Dann rate ich von dem Knoten v aus wieder einen Nachbarknoten u. Erhöhe meine Distanz wieder um 1. (Also ist die Distanz von dem Knoten jetzt 2). Das ganze mach ich solange bis ich irgendwann bei meinem Knoten ankomme, von dem ich behaupte, dass er erreichbar sei. Ist er erreichbar, dann verwerfe ich den ganzen kram. Ist er nicht erreichbar, habe ich im Prinzip gezeigt, dass es einen Knoten gibt, der nicht erreichbar ist.

Frage 1: Wenn der Knoten erreichbar ist, dann muss ich mir ja irgendwie merken, dass ich den Knoten schon besucht habe oder? Und wenn ja wie mach ich das, damit ich nur logSpace Platz verbrauche?

Antwort: Knoten werden bei LogSpace immer mit den Zahlen 1...n gemerkt, wobei die Zahlen binär dargestellt werden. So kann man mit einem Platz 2 Knoten darstellen. Mit 2 Plätzen 4 Knoten, mit 3 Plätzen 8 Knoten und so weiter. 0,1,10,11,100,101,110,111...

So weit wie ich das Immerman Theorem nun verstanden habe, zählt man nach jedem neuen Durchlauf von i (Also jedes Mal wenn i erhöht wird.) alle Knoten von vorne in c_i+1.

Und durch den Algorithmus ist es sichergestellt, dass man sich keinen Knoten lange merken muss, weil man immer alle Knoten von vorne aufzählt und sich nur die Summe dieser merkt. Da die innre und äußere Schleife so konzipiert ist, dass man immer alle Knoten durchgeht, ist es auch nicht nötig sich einzelne Knoten zu merken.
Man zählt eh immer wieder von vorne alle auf. Und da man das quasi sukzessiv, also auf dem Eingabeband der Reihe nach (von links nach rechts) durchgeht, ist es nicht nötig sich bereits besuchte Knoten zu merken, weil die im Prinzip auf dem Eingabeband links vom Lese/Schreib- Kopf stehen.
 
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »