On the Derandomization of Space-Bounded Computations
On the Derandomization of Space-Bounded Computations
复制标题
关于空间限制计算的去随机化
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
R. Armoni
中科院分区：
文献类型：
--
作者：
R. Armoni
我们使用Zuckerman的提取器[7]来构建一个伪随机的生成器，用于使用S空间的机器和R≤2S1-ɛ随机位，用于ɛ> 0。 log r）/ log s）比Nisan [4]的生成器和Nisan和Zuckerman的生成器短，然后我们使用此生成器将这些机器驱散在Space O（s√（log）（log（log） r）= log s）是比[6]的衍生物更好。
We construct a pseudo-random generator for space bounded computations using the extractor of Zuckerman [7]. For machines that use S space and R ≤ 2S1-Ɛ random bits for Ɛ > 0, the generator uses a seed of length O((S log R)/ log S) which is shorter than the seed of both the generator of Nisan [4] and the generator of Nisan and Zuckerman [5]. We then use this generator to derandomize these machines in space O(S√(log R)= log S) which is better than the derandomization of [6].