伪随机生成器复杂性研究与DLOGTIME均匀性应用

"本文探讨了构造伪随机生成器（PRG）的复杂性以及其在DLOGTIME-均匀性下的应用。研究集中在使用恒定深度电路来构造PRG，并分析了从硬函数出发构建PRG的可能性与限制。" 在计算复杂性理论中，伪随机生成器（PRG）是一种重要的工具，它能够将较短的随机种子扩展为更长的看似随机的序列，而在实际应用中，这些序列难以被有效区分于真正的随机序列。本文深入研究了如何利用恒定深度电路，即电路深度不随输入大小增加而显著增长的电路，来构造PRG。 作者首先展示了在DLOGTIME计算模型下，如何从一个特定类型的硬函数f出发，构建一个PRG。这个函数f能够在交替时间O(l)内计算，并且具有平均情况下对小电路的抗性。具体来说，如果f使得所有大小为2的电路在至少1/poly(1)的输入上无法计算f，那么可以构造一个PRG，它能够将O(log n)位的种子扩展到n位的输出，且这个PRG可以被DLOGTIME计算的常数深度电路处理。这一结果暗示在DLOGTIME-均匀性假设下，某些类别的计算等价性。 然而，作者也指出，从最坏情况下的硬函数出发，即存在某些输入使得所有小电路都无法正确计算的函数，无法构建出满足特定条件的PRG。具体地，对于任何常数δ<1，不存在一个PRG，它可以将δn位的输入扩展到n位的输出，并且能被常数深度电路计算。这是通过否定的构造证明得出的，即表明在这种情况下，无法实现有效的黑盒构造。 此外，文章还探讨了硬函数的“硬放大”问题，即从最坏情况的硬函数生成平均情况下的硬函数。作者证明，在多项式时间内不存在这样的黑盒构造，这涉及到证明恒定深度电路无法计算良好的提取器和列表可解码编码。 这篇文章揭示了构造PRG的复杂性和限制，特别是在恒定深度电路和DLOGTIME计算模型的背景下。它对理解计算复杂性理论中的伪随机性和电路效率提供了新的洞察，同时也为密码学和复杂性理论的研究提供了有价值的参考。关键词包括伪随机生成器、硬度、恒定深度电路、DLOGTIME均匀性和噪声敏感性。这些研究对进一步探索计算的界限和安全性的理论基础具有重要意义。