论文标题
关于无方向性的问题
On the Problem of Undirected st-connectivity
论文作者
论文摘要
在本文中，我们讨论了一种确定性和日志空间的无方向性st-conncontnectivity问题的算法，即Reingold在他的2008年论文“日志空间中的无向连接性”中的算法。我们进一步提供了Rozenman和Vadhan在L $中的$ \ text {ustConn} \的单独证明，并与Reingold的证明进行了讨论。已知无方向性的ST连接性是完整的，对于通过对称，非确定性，日志空间算法解决的复杂性类别的SL-问题。同样，Aleliunas等。 al。，众所周知，无向的ST连接性在RL复杂性类别内，通过随机（概率）图灵机可以解决的问题在对数空间和多项式时间内单方面误差。最后，我们的论文还表明，无方向性的ST连接性在L复杂性类别内，通过对数空间中的确定性图灵机可以解决的问题。从这个结果中引导，我们将解释为什么SL = L并讨论为什么认为RL =L。
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.
