计算复杂度下的伪随机发生器从硬函数构造与恒定深度电路的关系

布里尔Comput.复杂. 13（2004），147-DOI 10.1007/s00037-004-0187-12004年，BürcBirkhause r V erlag，Base l计算复杂度构造伪随机生成元从硬函数马努埃莱·维奥拉抽象。我们研究了从硬函数构造伪随机发生器（PRG）的复杂性，重点是恒定深度电路。我们证明了，从函数f：{0，1}l→ {0，1}开始，可在交替时间O（l）内计算，平均而言具有O（1）次交替（即， 有一个常数n> 0，使得每个大小为2的电路都不能在至少一个1/poly（1）分数的输入上计算f），我们可以构造一个PRG：{0，1}O （ log n）→ {0，1}n，可通过DLOGTIME计算-n中大小多项式的均匀常数深度电路。这样的PRG意味着在DLOGTIME -均匀性下BP·AC 0= AC 0。在消极的方面，我们证明了从最坏情况的硬函数f：{0，1}l→{0，1}（即存在一个常数n>0，使得每个大小为2的电路在某些输入上都无法计算f）开始，对于每个正的常数δ<1，不存在PRG：{0，1}δn → {0，1 } n的黑盒构造，该PRG：{ 0，1} δn可由n中大小为多项式的常数深度电路计算。我们还研究了最坏情况下的硬放大，这是一个相关的问题，产生一个平均情况下的硬函数从一个最坏情况下的硬。 特别是，我们推断，有没有黑盒的最坏情况下的硬度放大内的多项式时间神经网络。这些否定的结果是通过表明多项式大小的恒定深度电路不能计算好的提取器和列表可解码代码而获得的。关键词伪随机发生器，硬度，恒定深度循环，DLOGTIME均匀性，噪声灵敏度。主题分类。68Q01.1. 介绍在Blum Micali（1984）和Yao（1982）的开创性著作中引入了伪随机生成器（PRG）的严格概念，并在密码学和复杂性理论中找到了惊人的各种应用的PRG148维奥拉CC 13（2004）{} → {}.-x}n·{} → {}{} → {}{} → {}−{} → {}G：0， 1u0， 1n是将u个输入比特扩展成nu个输出比特的有效过程，使得PRG的输出从随机电路到小电路是不可区分的。也就是说，对于每个大小为n的电路A，PRx∈{0，1}u[A（G（x））= 1]Pr{0，1}[A（x）=1]。≤1/n。1在这项工作中，PRG的复杂性是根据其输出长度（上面表示为n）。虽然PRG的存在是一个主要的开放问题，但已经有一系列有趣的作品从越来越弱的假设中构建PRG。Nisan Wigderson（1994）展示了如何从强平均情况硬度假设（即布尔函数的存在性）构造PRG F级： 0， 1l0， 1 inE：=TIME（2O（l））这对于电路来说是很难平均的。 特别地，他们表明，从E中的函数f：0，1 l0，1开始，使得（对于某个常数ε > 0）大小为2 μ l的每个电路在输入的至少1/21/2 μ l分数上不能计算f，可以构造具有对数输入长度的PRG，即G：0，1O（logn）0， 1n，可计算的时间多项式n。具有对数种子长度的有效PRG特别令人感兴趣，因为正如我们下面讨论的，它们意味着BPP=P。 请注意，PRG G可在n中的时间多项式中计算，即使它是从可在指数时间中计 算 的 函 数 f （即，在E中）。这是这是可能的，因为G只在长度为l=O（logn）的输入上计算f由于Nisan Wigderson（1994）中的平均情况硬度假设似乎非常强，因此许多研究致力于在较弱的最坏情况硬度假设下构造具有对数种子长度的PRG，即存在函数f： 0、 1升0、 1个在E中，使得（对于某个常数ε >0）每个大小为2ε l 的电路在某个输入上都无法计算f（例如Babaiet al. 1993; Impagliazzo1995）。 这项研究在Impagliazzo Wigderson（1997）中达到顶峰，其中显示了如何放大最坏情况下的硬度在E中的函数的平均情况下，Nisan Wigderson（1994）所要求的硬度。我们在第3节中对这些结果进行了调查。Sudan等人（2001年）、Impagliazzo等人（2000年）、Shaltiel Umans（2001年）和Umans（2002年）提供了更直接的证明和改进的结果。[1]Blum Micali（1984）和Yao（1982）的原始定义不同之处在于，它要求每个多项式大小的电路在区分PRG的输出与随机方面具有可忽略的优势为了去随机化的目的，它是足够的，以固定一个通用常数c，并要求每个电路的大小nc有优势，最多1/nc在区分的PRG的输出随机。此外，由于电路可以忽略部分输入，我们可以设置c= 1。在本文中，我们采用后一种定义的PRG。构建PRG的复杂性149CC 13（2004）········⊆·{} → {}1.1. 我们研究的问题。在本文中，我们解决以下问题：什么是复杂的构造一个PRG从一个硬函数？研究这个问题至少有两个原因首先，我们想了解理论计算机科学中两个基本量之间的计算关系：硬度和随机性。第二，PRG是一个基本的工具，其各种应用证明了对越来越多的高效构造的追求去随机化一 个需要越来越多的有效PRG的重要应用是复杂性类C的高端去随机化，即证明BP C = C。 对于这样的应用，我们需要具有对数种子长度的PRG，如上所述，可以从具有指数电路复杂度的函数开始构建PRG。例如，英帕格利亚佐·&威格德森（英语：ImpagliazzoWigderson）（1997）证明了BPP = P，如果在E中有一个函数f：0，1 l0，1，需要大小为2 <$ （l ）的 电路。这种去随机化的工作原理如下。 我们使用PRG的所有可能输出来代替真正的随机位来运行我们想要去随机化的算法。然后我们根据多数票来决定由于种子长度是对数的，因此该过程是有效的，即， 只给出多项式减速。很明显，如果我们的目标是使用PRG去随机化概率复杂度类BPC，那么PRG必须在C中可计算。因此，我们想要去随机化的复杂性等级越低，PRG就必须越例如，为了对BPL（其中L：= SPACE（log n））进行去随机化，需要一个比Nisan &Wigderson（1994）中给出的、并在Impagliazzo &Wigderson（1997）中用于对BP·P进行去随机化的更有效的PRG构造。 这个问题由Klivans &van Melke-beek（1999）解决，他在假设有一个函数f：{0，1}l → {0，1}在线性空间中可计算，需要大小为2 <$（l）的电路的情况下得到BP · L = L。在本文中，我们研究了更有效的PRG结构，可用于去随机化低于BPL的概率类。特别地，我们的目标是证明BP AC0=AC0服从DLOGTIME-均匀性，其中AC0表示可由多项式大小的恒定深度电路计算的函数类，并且DLOGTIME-均匀性是下面讨论的强均匀性条件（在第1.2节的末尾）。请注意，高端去随机化BP AC0=AC0服从DLOGTIME-均匀性并不知道无条件地保持。实际上，弱包含P-一致BP AC0P是否正确仍然是开放的：P-一致BP AC0的最有效的无条件去随机化是由Nisan（1991）在准多项式时间内获得这样的德-150维奥拉CC 13（2004）{} → {}·⊆{} → {}{} → {}.····{} → {}≤{0，1}随机化是基于这样的事实，即L比特上的奇偶校验函数不能由大小为2LC的恒定 深 度 的 电 路 （ 在 平 均 值 上 ） 计 算 （其中L C是取决于电路深度的常数;参见例如，1987年）。另一方面，通过PRG证明P-均匀BP AC0P将需要展示E中的函数f：0，1 l0，1，其（对于某个常数f> 0）不能通过大小为2 l l的恒定深度电路来计算。但它与当前的知识状态是一致的，每个函数f：0， 1l0， 1 在E中，可由大小为2o（l）和深度为3的电路计算。应该注意的是，Valiant（1977）的一个结果指出，如果一个函数 F级：0、 1升0、 1个(for一些常数n>0）不能由大小为2的电路计算，那么它就不能由线性大小和对数深度的电路计算表现出不能在后一电路类中计算的线性尺寸和对数深度）是Valiant（1977）提出的一个1.2. 黑盒PRG构造。 正如我们在1.1节中所解释的，我们研究了从硬函数构造PRG的复杂性。我们现在讨论一下什么是“构建”。 一个预言过程Gf：{0， 1}u→{ 0， 1}n是一个由最坏情况的硬函数构造的黑盒PRG，如果对于每个函数f：{0， 1}l→{ 0， 1}且对于每个函数A：{0， 1}n→{ 0， 1}，如果A将PRG的输出与随机区分开，即. xPr}u[A（G（x））=1]−xPr [A（x）= 1]> 1/n，}n则存在大小为s的oracle电路C，给定对A的oracle访问，该oracle电路C在各处计算f，即对于每个x，CA（x）=f（x）。这个想法是，如果我们从一个函数f开始，使得没有大小为s n的电路可以在任何地方计算f（即f对于大小为s n是最坏情况下的困难），那么G是PRG。这是因为，如果一个大小为n的电路A将G的输出与随机数区分开来，那么CA就是一个大小为s n的电路，处处计算f，这与f的困难性相矛盾。注意，在黑盒PRG构造中，我们需要硬函数f的输入长度l为n（logn）。 否则，可以证明每个函数f：0，1 l0，1都可以由大小为2 l n的电路计算，因此我们关于f在大小为s n时是最坏情况困难的假设立即是错误的。上面定义的PRG构造被称为黑盒，因为它适用于每个函数f和每个潜在的函数A，而不管它们的复杂度如何。虽然可以想象非黑盒PRG构造比黑盒构造更强大，但我们注意到所有已知的PRG构造都是黑盒的，例如，BlumMicali（1984）; Yao（1982）; Impagliazzo Wigderson{0，1}构建PRG的复杂性151CC 13（2004）（ 1997 ） ;Klivans &van Melkebeek （ 1999 ） ; Sudan et al. （ 2001 ） ;Impagliazzo et al.（2000）; Shaltiel& Umans（2001）; Umans（2002），以及本文中的所有人。然而，非黑盒PRG结构被认为在均匀设置中比黑盒PRG结构更强大，即当我们只要求PRG的输出从随机到均匀机器（与我们的定义所要求的非均匀电路相反）无法区分时我们建议读者参考Trevisan Vadhan（2002）对这个问题的讨论。到目前为止，我们已经讨论了从最坏情况的硬函数的黑盒PRG结构。从平均情况下的硬函数的黑盒PRG结构是类似的，除了我们只需要CA计算f的平均值（而不是处处）。通过同样的推理，这足以确保Gf是一个PRG时，f是硬的平均。黑盒PRG结构在AC0。本文讨论的主要技术问题是：AC0中是否存在黑盒PRG结构？（回想一下，AC0表示可由多项式大小恒定深度电路计算的函数类正如我们在下面（1.3节）所解释的那样，在本文中，我们展示了关于这个问题的积极和消极结果无论AC 0的均匀性如何，我们的否定结果都适用，并且我们的肯定结果甚至在严格的均匀性条件下也成立，即DLOGTIME-均匀性，我们现在讨论。非正式地，一个家庭的电路是DLOGTIME-均匀的，如果给定索引的两个门，可以决定他们的类型，以及他们是否连接在线性时间的长度的索引（这是对数时间的大小的电路）。 有一个共识，这是AC 0的“正确”均匀性条件，证据是DLOGTIME-均匀AC0有几个不同的和优雅的表征;见Barringtonet al.（1990年）。我们在这项工作中经常使用的一个字符化是这样的：DLOGTIME-uniformAC0 等 价 于 ATIME （ O （ 1 ） ， logn ） ， 其 中ATIME（O（1），logn）表示交替时间O（logn）和O（1）交替（参见。定理2.2）。类ATIME（O（1），logn）由Sipser（1983）引入，是多项式时间层次（ATIME（O（1），nO（1）的对数模拟，并且严格包含在SPACE（logn）中。1.3. 我们的成果。表1总结了我们的一些结果，并与以前的结果进行了比较我们的主要发现是，存在由（轻度）平均情况硬函数构造的黑盒PRG结构Gf，使得Gf在ATIME（O（1），logn）f中可计算.但是，没有黑盒PRG结构Gf从最坏情况的硬函数，使Gf是可计算的小型非uniform的预言恒定深度电路。表1.1：我们的一些结果与以前的结果的比较（调用ATIME（O（1），logn）=DLOGTIME-uniformAC0。）硬度放大对于函数：{0， 1}l→ { 0， 1}强硬度对于PRG：{0， 1}O（logn）→{ 0， 1}nPRG构造的去随机化先前结果最差情况硬⇓强硬PRG的复杂性差情况硬度假设意味着可能两者都在TIME（2O（l））[定理3.3，3.4，3.5]在空间（O（1））中[定理3.7]时间（n，O（1））[定理3.2]时间复杂度O（logn）BP·P=P[定理3.5]BP·L=L[定理3.7]我们的结果最差情况硬⇓微硬微硬⇓强硬PRG的复杂性轻度平均病例硬度假设意味着不可能的O（1），O（1），O（2）如果黑盒[推论7.5]可能的时间复杂度O（1）[定理4.2]时间复杂度O（1）[定理4.1]时间复杂度O（1）ǁ时间复杂度O（1）（定理4.3，4.7）小行星152CC 13（2004）构建PRG的复杂性153CC 13（2004）≤·联系我们--{} → {}{} → {}联系我们--≥≥≥{} → {}≥≥{} → {}{} → {}积极的一面。我 们 展示了 是一个黑盒PRG结构 Gf：0， 1O（logn）0，1 n从轻度平均情况硬函数，使得G f在ATIME（O（1），log n）f中是可计算的，其中函数f：0，1 l0、 1个平均而言，如果有一个常数ε >0，大小为2 μ l的每个电路不能在输入的至少1/poly（1）分数上计算F。特别地，我们推导出，如果存在函数f：0，1 l，0、 1个在ATIME（O（1），l）中，平均来说是稍微困难的，那么存在a PRGG： 0、 1个时间复杂度O（logn）0，1n可在ATIME（O（1），logn）中计算，BP ATIME （O（1），logn）=ATIME （O（1），logn）。(When我们说G在ATIME（O（1），logn）中是可计算的，我们的意思是给定x和i n，我们可以在ATIME（O（1），logn）中计算G（x）的第i个输出位。实现这一结果的主要新技术工具是一个组合设计的结构，它可以在ATIME（O（1），logn）中计算。 我们还证明了在ATIME（O（1），l）中将弱平均硬函数放大到强平均硬函数是可能的，其中l是弱平均硬函数的输入大小此外，使用Agrawal（2001）的结果，我们表明，我们的PRG构造可以基于较弱的硬度假设，即存在一个函数，对于恒定深度电路是困难的（而上面的讨论是指对一般电路的硬度）。消极的一面。我们证明了，对于任意正的常数δ<1，任何来自最坏情况硬函数的黑盒PRG构造Gf：0，1 δn0，1 n，使得Gf可由一个具有常数深度的预言回路计算 并且大小g必须基本上满足（我们在这里省略一些低阶项）(1.1)logO（1）g≥ 2l/s，其中，我们从函数f：0，1L0，1开始，该函数对于大小为s的电路是最坏情况困难的。我们强调，即使当G的输入长度为u=δn时，不等式（1.1）也成立（回想一下我们的目标应该是u=O（logn））。为了理解不等式（1.1），我们必须回忆（在1.2节中）l≠（logn）。因此，当我们从一个不能用大小为s= 2<$l的电路计算的函数开始时，不等式（1.1）给出logO（1）g 2（1−<$）ln <$l（1），特别是黑盒PRG构造不能用大小为n的多项式的常数深度电路计算。我们还证明了这个界是紧的。另一方面，如果坚持在n中g多项式，则不等式（1.1）意味着我们必须从函数f开始：0，1 l0、 1个这是最糟糕的-用于尺寸为s的电路的硬外壳 时间复杂度O（1）2l/lO（1）。然而，我们表明，这个界限是如此之强，最坏情况和温和的平均情况的硬度154维奥拉CC 13（2004）{} → {}是等价的，在这个意义上，对于大小为2 l /l 0（1）的电路来说是最坏情况困难的每个函数f：0，1 l0，1实际上对于大致相同大小的电路来说是温和的平均情况困难。在这种情况下，可以使用我们的构造从温和的平均情况下硬函数构造PRG。从最坏情况硬函数出发，我们得到了平均情况硬函数的黑盒构造的类似的否定结果。这给出了表1中左下角的条目。 特别是，我们表明，从最坏情况下的硬函数f，有没有一个温和的平均情况下的硬函数计算的多项式时间层次的黑盒建设。再次注意，所有已知的方法都是黑箱，例如Babaietal.（1993 ）; Sudanet al.（2001 ）。然而，类似于PRG 构造（cf.第1.2节），已知非黑盒硬度放大在均匀设置中比黑盒硬度放大更强大，即当函数对于均匀机器（与非均匀电路相反）很难时。我们建议读者参考TrevisanVadhan（2002）对这个问题的讨论应该注意的是，黑盒最坏情况硬度放大的某些负面结果已经从我们以前的结果中得出。也就是说，如果存在黑盒最坏情况硬度放大，则将其与我们从轻度平均情况硬度的黑盒PRG构造相结合，得到来自最坏情况硬度的黑盒PRG构造，并且我们已经给出了否定的结果。然而，我们通过一个直接的证明得到了一个更一般的否定结果。讨论自 Impagliazzo& Wigderson（1997）以来，从最坏情况硬函数的PRG构造已经被简化和加强;参见Sudan et al. （2001）; Impagliazzo等人（2000）; Shaltiel &Umans（2001）; Umans（2002）。特别是，最新的结构不属于双重范式的“硬度放大+ Nisan-Wigderson PRG”，但直接将最坏情况的硬度转换为随机性。然而，我们的研究结果表明，最坏情况下的硬度转化为随机性的过程是双重的：黑盒最坏情况下的硬度放大比黑盒PRG从温和的平均情况下的硬度。我们的技术。我们现在概述一下负面结果背后的想法。我们对黑盒PRG结构的否定结果采用了以下思想。首先，我们使用Trevisan（2001）发现的事实（也可参见Trevisan Vadhan 2002; Shaltiel 2002），即黑盒PRG结构会产生“好的”提取器，这是Nisan Zuckerman（1996）介绍的然后，我们表明，恒定深度的电路不能计算对于这最后一构建PRG的复杂性155CC 13（2004）{} → {}{} → {}我们使用噪声灵敏度的概念，这是一个衡量函数的输出在输入被随机噪声干扰时改变的可能性的指标。 一方面，我们证明了提取器对噪声非常敏感，而另一方面，我们知道恒定深度电路对噪声不敏感（参见Linialet al.1993; Boppana 1997）。这种二分法确立了我们的否定结果。我们对黑盒最坏情况硬度放大的否定结果沿着类似的路线进行：首先，继Sudan等人（2001）和Trevisan Vadhan（2002）之后，我们表明黑盒最坏情况硬度放大会产生然后，我们表明，“好”的列表可解码的代码是非常敏感的噪声。同样，负面结果来自于恒定深度电路对噪声不太敏感的事实1.4. 其他相关工作。还有其他几个作品解决PRG的复杂性（除了我们已经提到的那些我们先讨论已知的负结果 Kharitonov等人（1989）和Yu &Yung（1994）证明了关于各种自动机和其他空间受限设备计算PRG的能力的强否定结果。 Linial等人（1993）证明了小的恒定深度电路不能计算伪随机函数（与PRG相关的对象）。Cryan Miltersen（2001）考虑了NC0中是否存在PRG的问题。然而，上述工作都没有研究从硬函数构造PRG的还应该指出的是，在线计算的提取器和列表可解码的代码的空间下界证明在酒吧Yossef等人。（2002年）的报告。然而，这些下限仅适用于在线计算模型，因此与我们的结果是不可比较的。现在我们讨论已知的PRG结构的正结果。已经有一系列关于从硬函数构 造 PRG 的 工 作 ： Impagliazzo&Wigderson （ 1997 ） ; Klivans &vanMelkebeek（1999）; Sudan et al.（2001）; Impagliazzo et al. （2000）;Shaltiel &Umans（2001）; Umans（2002）。在我们的论文之前，最有效的构造是Klivans van Melkebeek（1999）给出的构造，该构造构造了一个PRG：0， 1O（logn） 0， 1n，可在空间O（logn）中计算。注意，在本文中，我们考虑ATIME（O（1），logn）中的构造，ATIME（O（logn））是一个严格包含在空间O（logn）中的类。其他作品在假设某些特定问题很难的情况下给出了PRG的构造：Impagliazzo Naor（1996）展示了如何基于子集和问题的假设棘手性来构造PRG。特别是，他们展示了如何在AC0中构造PRG：0，1n−Θ（logn） 0， 1n。Naor Reingold（1997）给出了基于数论硬度的PRG构造，156维奥拉CC 13（2004）⊕{} → {}{} → {}选项。他们的PRG是可计算的多项式大小的常数深度电路与多数门（TC0）。1.5. Organization.在第2节中，我们给出了一些例子。在第3节中，我们回顾了以前从硬函数构造PRG的方法。在第4节中，我们描述了我们的主要结果。在第5节中，我们展示了如何从一个温和的平均情况下的硬度假设，在ATIME（O（1），logn）中构造一个PRG可计算。在第6节中，我们证明了我们的负面结果的黑盒PRG结构的最坏情况下的硬度假设。 我们还讨论了在何种意义上我们的结果是紧的。在第7节中，我们证明了黑盒最坏情况下的硬度放大的否定结果。在第8节中，我们放宽了对常数深度电路的硬函数的存在性的硬假设。 在第9节中，我们证明了一个关于恒深电路噪声灵敏度的引理，该引理在我们的否定结果中使用。最后，第10节讨论了一些开放的问题。2. 预赛复杂性 用ATIME（O（1），l）表示多带图灵机在时间O（l）内可计算的具有常数交替次数的函数类。(The图灵机有一个特殊的地址带。在给定的时间步上，机器可以访问由地址带的内容表示的输入位。这是为了处理小于输入长度的运行时间。） 我们有时利用下面的结果，通常归因于Ne pomnjasc i（1970）：这是M2。1（Nepomnj a pomnjapomnjc ipomnj 1970）. 对于y>0，如果f： 0、1升0、1个可以通过在时间poly（l）中运行并使用空间l1−l的算法计算，则f在ATIME（O（1），l）中。一个非线性函数f：{0，1}n→{0，1}NJisinATIMEE（O（1），l）if，对于每一个i，f的第i个输出位f（x）i在ATIME（O（1），l）中.注意，如果g：0，1 nJ0，1isinATIME（O（1），l）第n个函数g在ATIME（O（1），l）中f s als o。我们偶尔会考虑以下复杂度类：我们用CTIME（O（1），l）表示ATIME（O（1），l）的扩展，其中我们还允许计数量词（参见，例如，Wagner 1986; Toran 1988）。同样，我们用A TIME（O（1），l）表示ATIME（O（1），l）的扩展，其中我们也允许奇偶量词。我们现在定义一些用电路定义的复杂性类。本文中电路中所有的门都有无界扇入，只有一个例外构建PRG的复杂性157CC 13（2004）--有扇入的非门电路的大小是电路中边的数量。 我们用AC0表示可由多项式大小的常深与门、或门和非门电路计算的函数类。我们用TC0表示可由AND、OR、NOT和MAJORITY门的多项式大小的常数深度电路当 我 们 说 均 匀 时 ， 我 们 总 是 指 DLOGTIME- 均 匀 （ 参 见 ， 例 如 ，Barrington等人 1990; Vollmer 1999）。其他类型的均匀性（例如P-均匀性）总是明确规定的。Barrington等人（1990）证明了均匀AC0等价于ATIME（O（1），logn）（参见Vollmer 1999，Corollary 4.32）。同样的技术给出了我们上面定义的类的类似等价：THEOREM 2.2（Barrington等人， 1990）。 设f：{0，1}n→ {0，1}。◦ f是均匀AC 0当且仅当它是ATIME（O（1），log n）。◦ f是在均匀AC0与奇偶校验门当且仅当它是在时间复杂度为O（1）。◦ f是均匀TC 0当且仅当它是在CTIME（O（1），log n）。以下内容成立（参见，例如，Vollmer 1999，p. 161）：uniformAC0→uniformAC0 with PARITYgates → uniformTC0→ uniformL.前两个包含也适用于非均匀电路。关 于 电 路 复 杂 性 和 均 匀 性 的 背景 知 识 ， 读 者 可 以 参 考 AllenderWagner（1990）的调查和Vollmer（1999）的优秀教科书最后，对于一个复杂性类C，类BP·C由语言L和多项式p组成，对于语言L，V∈C，多项式p使得x∈L<$压力：|y|=p（|X|）[V（x，y）= 1] ≥ 2/3且x/∈ L<$Pr y：|y|=p（|X|）[V（x，y）= 1] ≤ 1/3。硬度和伪随机性。我们用Ul表示在0，1l上均匀分布的随机变量。我们用CKT表示由与门、或门和非门组成的电路类（没有深度限制）。我们用AC0[d]表示由AND、OR和NOT门组成的深度为d的我们用TC0[d]表示由AND、OR、NOT和MAJORITY门组成的深度为d的电路类设C是电路类（例如， CKT，AC 0[17]，. . . ）. 函数f：{0， 1}l→{0，1}对C是（g，δ）-难的，如果对每个长度至多为g的圈C∈ C，我们有Pr[C（Ul）=f（Ul）] <δ.158维奥拉CC 13（2004）..≤ ≤∩--联系我们最差情况硬度对应于δ=1。我们的平均情况硬度的阈值是中等平均情况硬度，对应于δ至多为1−1/lc。当我们说函数f：{0， 1}l→ { 0， 1}对于C是（2<$（l），1/ 2 + 2−<$（l））-难的时，我们的意思是存在一个常数<$0>0使得对于每个l，函数f：{0， 1}l→ { 0， 1}对于C是（2<$l，1/ 2 + 2−<$l）-难的。函数G：{0， 1}u→ { 0， 1}n是一个（n，n）-伪随机生成元(PRG)对C，如果对所有C∈ C的大小至多为n，我们有Pr[C（G（U u））=1] − Pr[C（U n）=1]≤ n。n-PRG是（n，1/n）-PRG.我们将u称为G的种子长度。3. 以前的PRG结构从硬函数在本节中，我们将回顾以前从硬函数构造PRG的方法。这个调查只需要了解我们更有效的PRG结构和我们新的去随机化结果。只对我们的否定结果感兴趣的读者可以安全地跳过这一节。我们从针对CKT的PRG开始（回想一下，CKT只是表示没有深度限制的标准电路）。然后，我们将重点放在PRG对恒定深度电路.3.1. PRG对抗CKT。 Nisan &Wigderson（1994）展示了如何从强平均情况硬度假设中构造PRG。 我们回顾了他们的PRG的定义，并陈述了他们的结果。D定义3.1（Nisan &Wigderson 1994）。 一个在大小为u的论域上大小为n的（m，l）设计是一个集合（S1，. . . ，Sn）的子集的集合。. . ，u}，每个都具有大小l，使得对于任何1I

下载后可阅读完整内容，剩余1页未读，立即下载