从stconn到循环的日志空间减少

Question

我读过这个帖子：显示周期是nl-complete？，但我不确定为什么减少是日志空间，因为它需要跟踪新图表，它具有 $ n ^ 2 $ 节点。

Answer 1

无需将新图形存储在磁带上。我们只需能够在LogSpace中输出它。对于任何合理的图形，这是简单的。