字符串柯尔莫哥洛夫复杂度近似理论及应用

1.Σ.Σ˜短时间内短节目的短名单Bruno Bauwens<$Anton Makhlin<$Nikolay Vereshchagin<$Marius Zimand<$摘要给定一台机器U，x的c-短程序是一个字符串p，使得U（p）=x，p的长度以c+（x的最短程序的长度）为界 我们表明，对于任何标准的图灵机，有可能在多项式时间内计算输入x的多项式大小的列表，保证包含O log |X|-x的短程序。 我们还证明了存在一个可计算函数它将每个x映射到一个大小列表|X|2包含一个O 1 -短程序的x。 这本质上是最优的，因为我们证明，对于每个这样的函数，有一个c和无限多个x，其中列表的大小至少为c|X|二、最后，我们表明，对于一些标准的机器，可计算函数产生列表与0-短程序，必须有无限经常列表大小成比例的2 |X|.关键词：列表近似器，柯尔莫哥洛夫复杂度，在线匹配，扩展图1引言字符串x的柯尔莫哥洛夫复杂度是计算它的最短程序的长度确定一个字符串的柯尔莫哥洛夫复杂度是一个不可计算函数的典型例子。与此密切相关的，也是不可计算的，是实际上为x生成最短程序的问题。人们自然会问，被这种不可能性障碍破坏的任务是否可以至少在某种近似意义上有效地解决这个问题已被调查的柯尔莫哥洛夫复杂性以各种方式。首先，众所周知，Kolmogorov复杂度可以从上面有效地近似。一种不同类型的近似由算法和复杂性理论中通常称为列表可计算性和可计算性理论中的可追踪性（枚举）给出。对于这种类型的近似，人们希望为函数的结果计算一个“可疑”列表，并保证实际结果在列表中。当然，列表越短，近似值越好。Kolmogorov复杂性C（x）的列表可逼近性已经由Beigel等人研究过[3]的文件。他们观察到，C（x）可以近似为一个大小为（n-a）的列表，其中n = |X|.另一方面，他们表明，对于每一个通用机器U，存在一个常数c，使得对于这项工作的扩展摘要已在2013年6月5日至7日在加利福尼亚州斯坦福举行的第28届IEEE计算复杂性会议上发表†国立研究大学高等经济学院。这项工作得到了NAFIT ANR-08- EMER-008-01项目的部分支持。莫斯科国立大学。这项工作得到了RFBR资助12-01-00864和ANR资助ProjetANR-08-EMER-008的部分支持;电子邮件：amakhlin@bk.ru§国立研究型大学高等经济学院。这项工作部分得到了RFBR赠款16-01- 00362的支持。电子邮件：ver@mccme.ru，WWW主页：http://lpcs.math.msu.su/ver.美国巴尔的摩陶森大学计算机与信息科学系电子邮件：mzimand@towson.edu;http：//triton.towson.edu/tummzimand。作者得到了NSF资助CCF 1016158的部分支持arXiv：1301.1547v3 [cs.CC] 2017年3月2一.Σ.Σ.Σ.Σ.Σ.Σ.Σ无限多个字符串x（实际上对于每个足够大的长度n至少有一个x），任何包含CU（x）的可计算列表的大小必须大于n/c。本文研究了短程序产生问题的列表可逼近性。为了为了描述我们的结果，我们需要几个正式的定义。O.1Σ机器U是最优的，如果C U（x|y）≤C V（x|y）+O 1对于所有机器V（其中常数可能取决于V）。最优机器U是标准1，如果对于每个机器V，总可计算函数t使得对于所有p，y：|t（p）|为|p| + O 1和U（t（p），y）=V（p，y），如果V（p，y）被定义. 对于在多项式时间内成立的结果，我们另外假设这些函数t可以在时间多项式中计算，|p|. 设U（p）表示U（p，空字符串），C U（x）表示C U（x|空字符串）。关于U的x的c-短程序是满足U（p）= x的字符串p，并且|p|≤ C U（x）+c。给定一个最优机器U，c-短程序的列表近似器是一个函数f，它在每个输入x上输出一个有限的字符串列表，使得列表中至少有一个元素是U上x的c-短程序。 让|f（x）|表示列表f（x）中元素的个数。显然，对于每个最优U，存在一个（平凡的）可计算列表近似器f，使得|f（x）|≤ 2 |X| +O1。我们研究的问题是，|f（x）|befor可计算列表逼近器f for c-短程序，其中c是常量或O log |X|. 乍一看，似乎在这两种情况下，|f（x）|一定是指数级的|X|.令人惊讶的是，事实并非如此。 我们证明了存在一个可计算逼近器，|X|2为c-短程序的一些常数c取决于选择的标准机U。我们证明了这个界是紧的。我们还表明，有一个多项式时间的可计算近似与列表的大小聚（|X|）for c-短程序for c= O log |X|.我们从主上界开始我们证明，对于每一个标准的机器，存在一个列表近似O 1 -短程序，具有二次大小的列表。定理1.1. 对于每个标准机器U，存在一个常数c和一个可计算函数f，对于任何x，f产生一个列表，|X|2许多元素包含一个长度为x的程序p |p|≤ C U（x）+c。常数c取决于U。下一个结果表明，这种依赖性是不可避免的。定理1.2. （1）对于每个c，存在一个标准的2机器U，使得对于每个可计算f，它是c-短程序的列表近似器：|≥e2|X|，对于某个常数e > 0和无穷多个x.|, for some constant e > 0 and infinitelymany x. 3（2）另一方面，对于每个c，有一个标准的2机器U，它有一个可计算的ap-具有大小列表的C-短程序的逼近器|X|二、（因为任何0-短规划的逼近器对于每个c ≥ 0也是c-短规划的逼近器，所以只有c = 0的情况才重要。因此，对于任何c，标准机器U是否具有用于具有多项式大小列表的c-短程序的可计算近似器的问题的答案取决于U的选择。如果我们允许O log |X|-短程序，我们可以在多项式时间内构造多项式大小的列表。[17]这不是一个简单的通过Schnorr[17]来实现的方法，并且我们称之为一个可计算的函数家族（从字符串到字符串）。我们使用不同的术语来区分Kolmogorov意义下的最优函数和Schnorr意义下的最优函数[2]这个构造意味着存在这样一个具有更强普适性的U：对于每个机器V，存在一个字符串wV，使得U（wVp）=V（p）对于所有p。3[3]对于c=0，这是由Frank Stephan [20]独立获得的4.Σ.Σ.- 是的 Σ. - 是的 Σ.Σ定理1.3. 对于每个标准机器U，存在一个多项式时间可计算函数f，对于任何x，它产生一个具有poly（|X|）许多元素包含长度为C U（x）+O log的x的程序|X|.Teutsch [22]改进了这个结果，|X| O 1。一个进一步的改进，使列表大小为O（|X|6 +ε）已由Zimand [29]获得。现在我们转到对所有标准机器都成立的下限。从Beigel等人的结果中可以很容易地得到c-短程序的任何可计算逼近器的列表大小”[3]前引事实上，如果存在一个可计算的列表近似器，x与大小为s（x）的列表，那么我们可以通过算法产生一个大小为s（x）c的列表，其中包含C（x）。（1）A= A（|X|），则s（x）=（|X|/c）。(The隐藏在符号中的常数取决于通用机器U。Bauwens [ 2 ]的一个结果也给出了一个线性下界，改进了Ga′ cs[6]的一个定理。 结果状态为所有单位机器U，CU（CU（x）|x）isgraaterthanlog |X|-O1，对于无穷多个x。因此，对于无限多个x的c-短程序的任何可计算逼近器f（x），日志|X|− O 1 ≤ C U（C U（x）|x）≤ log |f（x）|+2logc + O 1，并且因此|f（x）|1998年，|X|/c2）。注意定理1.1中列表大小的二次上限和线性下限上面描述的边界我们关闭这一差距表明，在定理1.1中的列表大小的界限是最佳的：它是不可能的计算列表的次二次大小，包含O 1 -短程序。定理1.4. 对于所有c>0，对于每个最优U，对于每个可计算f，它是c-短程序的列表近似器，|f（x）|1998年，|X|2/c2），对于无穷多个x。(The隐藏在符号中的常数取决于函数f和机器U。技术概述。字符串x的c-short程序是x的压缩表示;它也是一个（接近）最小长度的字符串，保留了x中的所有随机性。 这个想法来自于要想接近C-Short程序的列表近似性，就要使用随机性提取器。科尔-之前Fortnow，Hitchcock，Pavan，Vinodchandran，Wang，Zimand [5，8，26，27，28]已经研究了mogorov复杂性提取（也参见Zimand的调查论文[25]），并且实际上已经将用于恒定数量的独立源的随机性提取器用于该任务。对于c-short程序的列表近似性，使用种子提取器似乎很自然，因为通过迭代所有可能的种子，可以获得包含最佳压缩字符串的列表。问题是，我们需要一个具有对数种子的提取器（因为我们想要多项式大小的列表）和零熵损失（因为我们希望压缩的字符串是x的程序，即，以包含足够的信息，从而可以从其重构x），并且这样的提取器还没有被证明存在。也许令人惊讶的是，满足比提取器图要求更低的组合约束的更简单的图对于c-短程序的列表近似（以及对于这种类型的“列表”-柯尔莫哥洛夫复杂性的提取）是足够好的。受Musatov，Romashchenko和Shen [15]工作的启发，我们使用允许在线匹配的图这些是不平衡的二分图，在它们的最简单形式具有LEFT={ 0， 1}n， RIGHT={ 0， 1}k+小开销，以及左次数= poly（n），并且其允许在线匹配直到大小K=2k。这意味着任何一组K个左节点，每个可以以在线方式满足一个与先前未分配的某个相邻右节点匹配的请求（即，请求一个接一个地到达，每个请求都在看到之前得到满足5.Σ.Σ下一个;在我们的一些证明中，我们将允许少量的请求被丢弃，但这也应该在下一个请求到达之前发生与我们的问题大致对应的是，左字符串是我们想要压缩的字符串，对于任何左x，我们在它的右邻居中寻找它的压缩形式。 为了理解这种对应关系，让我们考虑一个更简单的情况，产生包含用于x的c-短程序的短列表，如果程序知道n = 1，|X|.同样，让我们假设x的Kolmogorov复杂度是k。我们开始枚举由k位产生的字符串程序，并且当枚举长度为n的字符串（最终为x）时，我们使用在线匹配过程并在其右邻居中找到它的匹配，即，我们将其压缩到长度k+小开销。为了进行匹配，我们从一个右节点（压缩字符串）开始，重新播放枚举和匹配过程，看看哪个左节点与它匹配;我们输出这个左节点。x的压缩程序在其右邻居中，因此x的右邻居的集合是多项式大小的期望列表。现在，实际上，n和k都不知道，因此我们实际上需要二分图是无限的，并且对左节点x的匹配请求包含所需的（k+开销）长度。经过这种修改，事实证明，该骗局-构造c-短程序的列表近似器f等价于构造一个无限二部图G，它能满足开销为c+O 1的在线匹配请求.列表f（x）的大小等于x在G中的次数。这样的无限图是通过取上述类型的有限图的并集而获得的为了使有限图允许匹配，它需要具有良好的扩展属性。事实证明，如果大小为K/O1的左子集扩展，尺寸K。为了得到定理1.1中需要的图，我们使用概率方法（实际上是为了得到二次左度数，我们需要改进上面勾画的结构）。定理1.3中所需的显式图是从Ta-Shma，Umans和Zuckerman [21]构造的分散器中获得的定理1.4中的下界是由上述列表可逼近性与在线匹配图的等价性建立的。接下来观察到，能够满足甚至离线匹配的二部图需要具有一定的扩展性质，这对左度施加了下限，正如我们所看到的，对应于列表大小。定理1.2中的指数下界使用与一种不太为人所知的Kol- mogorov复杂度类型的连接来示出，即总条件Kolmogorov复杂度，然后使用博弈论方法来构建具有大的这种复杂度的字符串。(The递归理论中基于博弈的技术由Lachlan [10]引入，并由A.Muchnik等人[12，23，18]进一步发展。纸组织。第二节研究了列表可逼近性与在线匹配图之间的关系。本文给出了关于具有在线匹配的图的定理2.5、2.6和2.7，并证明了它们分别蕴含定理1.1、1.3和1.4上界，即，定理2.5（因此定理1.1）、定理2.6（因此定理1.3）和定理1.2（2）在第3节中得到证明。下限，即，定理2.7（因此是定理1.4）和定理1.2（1）在第4节中得到证明。在第5节中，我们观察到我们的技术可以用来改进Muchnik定理[ 11 ]（也可参见Musatov，Romashchenko和Shen的工作[15，13，14]），以及2用于短程序和在线匹配的列表近似器我们表明，问题的构造逼近短程序是等价于构造- ING家庭的二分图，允许在线匹配，一个概念介绍了在一个有点不同的形式中的文件Musatov等人。[15 ]第10段。6.Σ.Σ设二部图G=（L，R，E<$L×R），其中左节点集L和右节点集R均由二进制串组成.假设我们在图中接收如果我们可以为左节点x分配一个长度不大于k的右邻居加上一个小的开销，这样的请求就得到了满足。对于任意x ∈ L，可能有多个请求（x，k1），（x，k2），. . . 因此，左节点X可以接收作为匹配的几个右节点。另一方面，右节点不能匹配多个左节点。对于每一个k，对于不同的x∈L，最多有2k个形式为（x，k）的请求。无法撤消验证。我们有时会把右节点称为哈希值。定义2.1. 设c（n）是n的自然值函数。一个二部图G=（L，R，E<$L×R），其左、右节点都是二进制串，如果下列条件成立，则G有开销为c（n）的对于每一个对（x，k）的集合S<$L× N，其最多具有2k个对，对于所有k，第二分量为k，可以为S中的每一个对（x，k）选择x的邻居p（x，k），使得|p（x，k）|C++=（|X|当x1/= x2时，p（x1，k1）/= p（x2，k2）. 对于某个x，允许p（x，k1）=p（x，k2）.如果这样做了，我们说p（x，k）匹配x。一个二部图有在线匹配，开销为c（n），如果这可以以在线方式完成：匹配（x，k）的请求一个接一个地出现，我们必须在下一个请求出现之前找到p（x，k）所有已分配的任务都不能更改。一个二分图具有可计算的（相应地，多项式时间可计算的）在线匹配，开销为c（n），如果它具有在线匹配，并且匹配策略是可计算的（相应地，如果左节点x的匹配可以在时间多项式中找到，|X|）. 我们假设该图可用于匹配算法。定义2.2. 一个二分图是可计算的（多项式时间可计算的），如果给定一个左节点x，我们可以计算（分别计算时间多项式，|X|）它的所有邻居的列表。多项式时间可计算图也被称为显式图。接下来的两个定理表明，对于任何函数c，存在一个可计算的（多项式时间可计算的）列表逼近器f，c（|X|）-短程序等价于存在一个可计算（多项式时间可计算）图G，该图G具有与开销c（|X|）+O 1和|等于x在G中的次数;直到对匹配的可计算性的假设|is equal to the degree of x in G; up to anassumption on the computability of the matching战略定理2.3（图G具有在线匹配的列表逼近器f）。假设存在具有L={0，1}的可计算的分组，其中左节点x具有D（x），并且其中具有与开销c（n）相关的线性映射。进一步假设匹配策略是可计算的。那么对于每一个标准机器U，存在一个可计算函数f，对于任意x，它产生一个具有D（x）许多元素的列表，该列表包含一个长度为x的程序p|p| C =C U（x）+C（|X|）+O1。如果图是多项式时间可计算的，那么函数f也是多项式时间可计算的。证据 回想一下，对于多项式时间的结果，我们假设一台机器是标准的，通过一个函数可以在多项式时间内计算。对所有字符串q并行运行最优机器U（q）。一旦U（q）在结果x处停止，我们就传递请求（x，|Q|）到图中的匹配算法，并找到长度至多为p的散列值|C++（|X|）对于x。|) for x.通过构造，每个字符串x都匹配到长度至多为C U（x）+c的字符串p（|X|）的。每个右节点最多与图中的一个节点匹配。因此，存在一台机器V，使得V（p）=x，只要p与x匹配。 因此，对于每个字符串x，都有x的邻居p，|p|C ++ C（|X|）和V（p）=x。由于U是一个标准机器，存在一个（多项式时间）可计算函数t，7.Σ.Σ.Σ121在一般性的情况下，我们认为f（x）中的所有字符串都有一个最小值，|X|+O。.1张照片和一张照片U（t（p））=V（p），|t（p）| ≤ |p| + O 1。设f（x）是由所有邻居p的t（p）组成的列表图中的x 施工|f（x）|= D（x），我们就完成了。定理2.4（具有在线匹配的列表近似f-图G）. 假设c（n）是（多项式时间）可计算函数，并且存在最优机器U和（多项式时间）可计算函数f，对于任意x，f产生包含长度为x的程序p的有限列表|C++ C（|X|）的。|). C onde rthebipartitegraphGw it hL={0，1}，其中节点x的中间值都是来自f（x）的字符串。则G具有与开销c的在线匹配（|X|）+O 1。证据 设G是G的子图，L ={0，1} ≤n，R是L的邻域集.图Gn是有限的。我们称G n具有与开销c的在线匹配（|X|）+O 1（其中O 1常数不依赖于n）。对于所有n，我们首先证明这蕴涵定理。 假设M1，M2，. . . 是图G1，G2，. . . 将它们转化为策略M′，M′，. . . 对于G1，G2，. . . 使得对于1 2所有i，j>i策略M′是M′的扩张，即在一系列只包含节点的请求上，J IGi，策略M′的行为与M′完全相同。因为每个Gn都是有限的，所以只有100个不同的J IGn的匹配策略因此，存在一个策略M′。这等于Mn到G1的限制，无限多的;无穷多的 因此也有一个策略M′这是M′且等于所述限制Mn到G2的次数是无限的，等等。它仍然显示索赔。 为了矛盾起见，假设对于每个常数i，存在n使得G n不具有与开销c的在线匹配（|X|）+i，且f是c的列表近似器（|X|）-短期节目在美国。 因为G n是有限的，对于所有n和c，可以通过算法（使用穷举搜索）找到G n是否具有开销c的在线匹配（|X|）+i或不。你也可以为获胜的玩家找到一个获胜的策略（因此，对于每一个i，我们可以算法上找到第一个n，使得图Gn不具有开销的在线匹配C=（|X|）+i和相应的获胜策略.让该策略与匹配器的以下“盲”策略进行博弈 接收到请求（x，k），匹配器对所有p ∈ f（x）运行U（p），|p|C ++=（|X|）+i，并行。如果对于某个p，U（p）停止，结果x，他将第一个这样的p与x匹配，并继续进行下一个请求。否则，该请求仍不满足。考虑下面的机器V。 在输入（q，i）上，其中q是k位长字符串，i是自然数，它找到第一个Gn，使得图Gn不具有开销c的在线匹配（|X|）+i和一个获胜的策略，并运行它对盲策略的匹配器。然后它返回x，其中（x，k）是第q个请求，第二个组件是k（我们以某种标准方式将字符串q解释为请求的序号）。由于获胜者获胜，因此存在未满足的请求（x，k）。我们有CU（x）≤CV（x）+O.1Σ≤k+2logi+O.（1）最后一个不等式对所有足够大的i成立。由于请求（x，k）未被满足，因此f（x），|p|01- 02 - 2016刘晓波（|X|）的。 （1）如果x = 0，则x = 0（|X|）-x的短程序，一个矛盾。我们把c-短程序的列表近似问题归结为构造具有多项式左次数的在线匹配的二部图我们的主要技术贡献是以下定理。2.5（与1. 5相比，①的人。这是一个简单的可移植的图，其中hL={0，1}anddleftdegreD（x）=|X|2.在整个O上没有时间限制。1美元。8定理2.6（定理1.3的组合版本）。有一个多项式时间可计算图，其中hL={0，1}，其中hleftdegreeD（x）=poly（|X|（我不知道他有没有时间和他在一起。高架O.日志|X|- 是的定理2.7（定理1.4的组合版本）。在L= {0，1}n的图G中，若图G具有开销为c的离线匹配，则其左结点的最大度为<$（n2/c2）。定理2.5、2.6和2.7分别蕴涵定理1.1、1.3和1.4我们在定理2.5和2.6的证明中使用的在线匹配策略非常简单：接收形式为（x，k）的新请求，我们只需找到最大i≤k+c，使得存在一个自由（即，还没有在匹配中使用）长度为i的x的右邻居，并将x与x的第一个这样的邻居匹配。3上界在本节中，我们证明了定理2.5、定理1.2（2）和定理2.6。从本质上讲，证明包括在建设相应的图，具有在线匹配的开销c（n）。这些是无限图，它们是由具有L= {0， 1}n的有限二分图的并集得到的， R={0， 1}k+c（n）. 对于这样的图，其中正确节点的长度是固定的，我们不需要像定义2.1中那样在匹配请求中引用长度约束，并且我们可以使用以下内容更简单的定义。定义3.1. 一个二分图有匹配到K，最多有M个拒绝，如果对于任何一组最多为K的左节点，我们可以删除最多M个它的元素，使得在图中有一个匹配到剩余节点的集合。一个图有一个在线匹配到K，最多有M个拒绝，如果我们能以在线方式做到这一点。当M=0时，我们说图的匹配度达到K。图与图之间的连接（在线）匹配到K（定义3.1）和图（在线）匹配与开销c（定义2.1）如下。如果一个图G具有开销为c的（在线）匹配，则从G中移除长度不同于n的所有左节点和长度为长度大于k+c（n），我们得到一个图（在线）匹配高达2k。另一方面，假设对某个n，对所有的kn，我们有一个图Gn，k，其中L= {0， 1}n，R= {0， 1}k+c（n），它（在线）匹配到2k。< 则Gn，k在所有 |X|-3。该图具有恒定开销的在线匹配这可以用向下归纳法证明，如定理3.4所示。实际上，考虑第s个匹配请求到达时的步骤通过对k的向下归纳，我们可以再次证明在Hk中匹配请求的数量至多为2k+1。现在归纳的基础是最大的k，在s个请求中至少有一个请求在Hk中匹配。我们得出结论，第s个请求得到了满足，因为这对每个s都成立，所以我们完成了。正如我们已经看到的，定理2.5蕴涵定理1.1。如果∑12n32N33.2定理1.2的证明（2）根据定理2.5，存在具有可计算在线匹配策略的可计算图G，其开销c和度为常数|X|二、固定任何标准机器U。在定理2.3的证明中，我们构造了一个可计算函数V，使得CV（x）≤CU（x）+c，并且使得每个字符串x的每个V-程序都是图G中x的邻居。 如果碰巧V是一台标准机器，那么我们就完成了：考虑列表{p |p是x的邻居。否则，定义机器U1，让U1（0p）=V（p）和U1（1c+2p）=U（p）。 第二方程式保证U1是一台标准机器。这两个方程都意味着对每个x，x的0-最短U1-程序的形式为0p（回想CV（x）≤CU（x）+c）。因此，对于所有x，0-最短U1-程序q对于列表{0 p}中的x|p是x的邻居。3.3定理2.6的证明由定理3.4，我们必须对每个k≤n构造左次poly（n）的一个显式（2k，2k）-扩张子，其中左结点为2n，poly（n）右结点为2k（回想一下，如果有一个算法在输入x∈ {0， 1}n=L上在poly（n）时间内列出x的所有邻居，则该图是显式的。证明依赖于下面Theo-rem3.8中Ta-Shma、Umans和Zuckerman的显式分散图。定义3.7. 一个二部图G =（L，R，E）是一个（K，δ）-分散子，如果每个子集B <$L，|B|≥ K至少有（1 − δ）|R|不同的邻居定理3.8. [Ta-Shma，Umans，Zuckerman [21]]对每个K，n和常数δ，存在一个显式（K，δ）-分散子G =（L ={0，1}n，R ={0，1}m，E <$L × R），其中L中的每个节点的度D = poly（n），|R|= αKD，对于某个常数α。给定n和k，我们将该定理应用于K=2k和δ=1/ 2。 我们得到了一个（2 k，α2k D）-扩张子，它的次数D= poly（n），L= {0，1}n，|R| =αKD。考虑t=max{ 1，n2n3n n}个不相交的副本，n3αD图，并识别结果图的左节点（保持它们的右节点集不相交）。我们得到一个显式的（2k，2k）-扩展器，有2n个左节点和2k个右节点，度为poly（n）t=poly（n）.正如我们已经看到的，定理2.6蕴涵定理1.3。4下界4.1定理2.7的证明假设G具有与开销c的离线匹配。设G[k，k]表示从G中去掉所有长度大于k且小于k的右结点而得到的导出图。图G[0，k+c]显然是一个（2k，2k）-扩张器，对每个k.由于长度小于k−1的字符串少于2k− 1个，因此图G[k−1，k+c]是一个（2k， 2k−1+ 1）-扩张器。由Kovarisri，So`s和Tura`n[9]（见Radhakrishnan和Ta-Shma[1.6，定理1.5]）提出的一个概念表明，任何这样的扩张子都必须有大的次数。引理4.1. 假设一个有2个k左节点和2个k+c右节点的二部图是一个（2 k，2 k−1+ 1）-扩张图。 然后在图中有一个左节点，其度大于D = min {2 k−2，（k − k）/（c +2）}。13.Σ2k−1.Σ.k+c.Σ证据 为了避免矛盾，假设所有左节点的度最多为D（并且在不失一般性的情况下，我们可以假设所有的度都是D）。我们需要找到一组大小为2k−1的右节点B和2k个左节点，它们的邻居都在B中。集合B是通过概率建设 即，随机选择B（所有2k+c 概率相等）。 的概率一个固定的左节点的固定邻居在B中等于2k+c−D2k−1−D=22k−12k−1（2k−1−