3.4.4 L = NL? 与 NL = co-NL (Immerman–Szelepcsé...

文档摘要

3.4.4 L = NL? 与 NL = co-NL (Immerman–Szelepcsényi Theorem) 3.4.4 L = NL? 与 NL = co-NL (Immerman–Szelepcsényi Theorem) 想象一下，你手握一张巨大的迷宫地图，只用一张小纸条记录路径，就能判断起点是否能抵达终点。这就是非确定性对数空间（NL）的魅力所在。它不像多项式时间那样奢侈，而是以惊人的空间节俭，探索图的连通性。但如果迷宫不存在路径呢？co-NL的问题就来了：如何证明“无路可走”？1987年，Neil Immerman和Róbert Szelepcsényi同时独立证明了 $NL = co-NL$，这不仅是理论计算机科学的一次优雅胜利，还为我们提供了可实现的算法框架。