Pseudorandom Walks in Directed Graphs and the RL vs. L Question [1/3]

Опубликовано 6 сентября 2016, 5:28

A long-standing open question in complexity theory is whether there are problems that randomized algorithms can solve using (asymptotically) less space than possible by any deterministic algorithm. An important special case of this question was recently resolved by Reingold (STOC `05), who gave a deterministic log-space algorithm for S-T Connectivity in Undirected Graphs, by derandomizing the known randomized log-space algorithm of Aleliunas et al. (1979). Motivated by Reingold's result, we revisit the general question of whether randomized log-space (RL) equals deterministic log-space (L). We show that to prove RL=L, it suffices to construct a pseudorandom