Protokollraumreduzierung von STCONN bis zum Zyklus

Question

Ich habe diesen Beitrag gelesen: Zyklus zeigt NL-Complete? , aber ich bin nicht sicher, warum die Reduktion des Protokollraums ist, da es erforderlich ist, die neue Grafik zu verfolgen, die $ N ^ 2 $ Knoten aufweist.

Answer 1

Es ist nicht erforderlich, das neue Graph auf dem Band aufzubewahren.Wir müssen nur in der Lage sein, es in Logspace auszugeben.Dies ist unkompliziert, für jede vernünftige Kodierung von Graphen.