Reproducibility and Pseudo-Determinism in Log-Space
Reproducibility and Pseudo-Determinism in Log-Space
复制标题
对数空间中的再现性和伪决定论
DOI：
10.1137/1.9781611975482.38
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Yang P. Liu
中科院分区：
文献类型：
--
作者：
O. Grossman;Yang P. Liu
随机对数空间搜索算法的一个奇怪特性是，它们的输出通常比它们的工作空间长。这就引出了一个问题：我们如何在不逐字存储输出或随机性的情况下再现随机化日志空间计算的结果？使用新的随机比特再次运行算法可能会产生新的（可能不同的）输出。
A curious property of randomized log-space search algorithms is that their outputs are often longer than their workspace. This leads to the question: how can we reproduce the results of a randomized log space computation without storing the output or randomness verbatim? Running the algorithm again with new random bits may result in a new (and potentially different) output.
We show that every problem in search-RL has a randomized log-space algorithm where the output can be reproduced. Specifically, we show that for every problem in search-RL, there are a pair of log-space randomized algorithms A and B where for every input x, A will output some string t_x of size O(log n), such that B when running on (x, t_x) will be pseudo-deterministic: that is, running B multiple times on the same input (x, t_x) will result in the same output on all executions with high probability. Thus, by storing only O(log n) bits in memory, it is possible to reproduce the output of a randomized log-space algorithm.
An algorithm is reproducible without storing any bits in memory (i.e., |t_x|=0) if and only if it is pseudo-deterministic. We show pseudo-deterministic algorithms for finding paths in undirected graphs and Eulerian graphs using logarithmic space. Our algorithms are substantially faster than the best known deterministic algorithms for finding paths in such graphs in log-space.
The algorithm for search-RL has the additional property that its output, when viewed as a random variable depending on the randomness used by the algorithm, has entropy O(log n).