Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace
Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace
复制标题
有针对性的伪随机生成器、模拟建议生成器和去随机化日志空间
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
C. Umans
中科院分区：
文献类型：
--
作者：
William M. Hoza;C. Umans
假设对于Logspace算法的每个降低结果，都有一个伪随机的发电机，足以通过对所有种子进行迭代并以多数投票的方式恢复降低。 （log1 +αn）对logspace的发电机作为输入一个均匀的随机种子和有限的自动机；有一些logspace算法，给定有限的自动机和此建议字符串，模拟了自动机读取长统一的随机输入。 PRBPSPACE（log1 +αN）=∩α> 0 prdspace（log1 +αn），并且仅当针对logspace的每个目标pseudorandom生成器时，就有一个模拟logspace的模拟咨询器，我们最终会观察到该参数。某些统一设置（即，如果我们只担心可以在logspace中生成的自动机序列），则可以将针对Logspace的靶标生成器转换为带有的模拟建议生成器，相似的参数。
Assume that for every derandomization result for logspace algorithms, there is a pseudorandom generator strong enough to nearly recover the derandomization by iterating over all seeds and taking a majority vote. We prove under a precise version of this assumption that BPL ⊆ ∩α > 0 DSPACE(log1 + α n). We strengthen the theorem to an equivalence by considering two generalizations of the concept of a pseudorandom generator against logspace. A targeted pseudorandom generator against logspace takes as input a short uniform random seed and a finite automaton; it outputs a long bitstring that looks random to that particular automaton. A simulation advice generator for logspace stretches a small uniform random seed into a long advice string; the requirement is that there is some logspace algorithm that, given a finite automaton and this advice string, simulates the automaton reading a long uniform random input. We prove that ∩α > 0 prBPSPACE(log1 + α n) = ∩α > 0 prDSPACE(log1 + α n) if and only if for every targeted pseudorandom generator against logspace, there is a simulation advice generator for logspace with similar parameters. Finally, we observe that in a certain uniform setting (namely, if we only worry about sequences of automata that can be generated in logspace), targeted pseudorandom generators against logspace can be transformed into simulation advice generators with similar parameters.