Randomness vs. time: de-randomization under a uniform assumption
Randomness vs. time: de-randomization under a uniform assumption
复制标题
随机性与时间：统一假设下的去随机化
DOI：
10.1109/sfcs.1998.743524
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
A. Wigderson
中科院分区：
文献类型：
--
作者：
R. Impagliazzo;A. Wigderson
我们证明，如果BPP/SPL NE/EXP，那么BPP中的每个问题几乎都可以在次指定时间中确定性解决（几乎每个输入（对于无限多个输入大小的每个可采样集合）。这是基于统一的非放映硬度假设的BPP的第一个降低结果。它暗示了BPP中问题的平均含量复杂性中的以下差距：这些复杂性始终是次指数的，或者它们包含任意大的指数函数。我们使用来自EXP中“硬函数”的小“假”字符串的构造，该字符串与前面所述的类似的非均匀结果中使用的字符串相同。但是，以前的正确性证明假定“硬函数”不在p/poly中。他们给出了一个非结构性论点，即将伪随机字符串与真正随机字符串区分开的电路意味着存在类似尺寸的电路计算“硬函数”。我们的主要技术贡献是表明，如果“硬函数”具有某些属性，那么可以使该论点具有建设性。然后，我们表明，假设ESP/SPL Sube/p/poly具有这些属性的Exp complete功能。
We prove that if BPP/spl ne/EXP, then every problem in BPP can be solved deterministically in subexponential time on almost every input (on every samplable ensemble for infinitely many input sizes). This is the first derandomization result for BPP based on uniform, noncryptographic hardness assumptions. It implies the following gap in the average-instance complexities of problems in BPP: either these complexities are always sub-exponential or they contain arbitrarily large exponential functions. We use a construction of a small "pseudorandom" set of strings from a "hard function" in EXP which is identical to that used in the analogous non-uniform results described previously. However, previous proofs of correctness assume the "hard function" is not in P/poly. They give a non-constructive argument that a circuit distinguishing the pseudo-random strings from truly random strings implies that a similarly-sized circuit exists computing the "hard function". Our main technical contribution is to show that, if the "hard function" has certain properties, then this argument can be made constructive. We then show that, assuming ESP/spl sube/P/poly, there are EXP-complete functions with these properties.