In this paper, we discuss an algorithm for the problem of undirected st-connectivity that is deterministic and log-space, namely that of Reingold within his 2008 paper "Undirected Connectivity in Log-Space". We further present a separate proof by Rozenman and Vadhan of $\text{USTCONN} \in L$ and discuss its similarity with Reingold's proof. Undirected st-connectively is known to be complete for the complexity class SL--problems solvable by symmetric, non-deterministic, log-space algorithms. Likewise, by Aleliunas et. al., it is known that undirected st-connectivity is within the RL complexity class, problems solvable by randomized (probabilistic) Turing machines with one-sided error in logarithmic space and polynomial time. Finally, our paper also shows that undirected st-connectivity is within the L complexity class, problems solvable by deterministic Turing machines in logarithmic space. Leading from this result, we shall explain why SL = L and discuss why is it believed that RL = L.
翻译：在本文中,我们讨论一个确定性和日志空间的非方向连接问题的算法,即Reingold在其2008年的论文“Log-Space中无方向连接”中的Ringold。我们进一步介绍了Rozenman 和 Vadhan 单独证明$\ text{USTCONN}在L$ 里,并讨论其与 Reingold 证据的相似性。已知非方向连接对于复杂类 SL- 问题之所以完整,是因为对称性、非确定性、 日志- 空间算法。类似地, Aleliunas 等人也指出,已知非方向连接性连接性在RL 复杂类别中, 由随机( 概率性) 开动机器与对数空间和多线性时间中出现单向错误而引起问题。最后,我们的文件还显示, 不可方向连接性连接性St- 连接性在对称性、 非确定性、 非确定性、 日志、 空间算算算算法中的问题。同样, 确定性 Turing 机器为何在逻辑空间里会解释。
相关内容
微信扫码咨询专知VIP会员