二进制字符串的最短描述的有效算法和近似值的存在

短时间杰森·特伊奇2018年11月15日，抽象。有没有可能找到一个二进制字符串的最短描述？众所周知的答案是“不，Kolmogorov复杂性是不可计算的。面对这一障碍，人们可能会寻求一个简短的候选人名单，其中包括简洁的描述。值得注意的是，这样的近似值是存在的。本文提出了一种有效的算法，它产生一个多项式大小的列表包含一个最佳的描述，为一个给定的输入字符串。一路上，我们采用扩展图和随机分散器，以获得一个显式的二部图的在线匹配定理和改进的Muchnik我 们 的 主 要 结 果 扩 展 了 Bauwens ， Mahklin ， Vereschchagin 和Zimand最近的工作。关键词Kolmogorov复杂度，在线匹配，二部扩展图，分散图，Muchnik主题分类。 68Q30、68R101. 对简短描述的追求我们探讨了随机性提取，combi- natorics，和Kolmogorov复杂性之间的相互作用，最终在一个有效的，新的近似最佳描述。非正式地说，一个计算机程序p被称为二进制字符串x的描述，如果p的执行产生输出x。 二进制字符串的柯尔莫哥洛夫复杂度（Kolmogorov complex）是它在某些标准编程语言中的最短描述的长度（见第2节）。尽管人们可能很想知道给定字符串的Kolmogorov复杂度，但它arXiv：1212.6104v5 [cs.CC] 2014年2月2杰森·托伊奇| |||⟨··⟩不可能有效地获得这个数量[5]。即使估计给定字符串的柯尔莫哥洛夫复杂度也是不可行的，因为没有无界的可计算函数可以是柯尔莫哥洛夫复杂度的下界[11，定理1.6]。此外，任何将一个字符串映射到一个包含其柯尔莫哥洛夫复杂性的值列表的算法，对于除n以外的所有长度n，必须在长度n的某个字符串的列表中至少包含n + O（1）以下长度的一个固定分数。值得注意的是，正如Bauwens，Makhlin，Veresh-chagin和Zimand最近观察到的那样[1]，当我们寻求短期时，情况有所不同给定字符串的候选描述列表。 我们将证明可以有效地计算多项式大小列表，对任何给定的字符串进行最短的描述，直到一个附加的常量位数（推论8）。我们的列表- ING算法的存在将遵循从组合图的建设，即我们的显式在线匹配定理，我们致力于我们的讨论的其余部分，以建立这个关键的结果。第2节和第3节提供了背景和先前的结果。第4节讨论了我们将用来获得第5节中的主要定理的二部扩张图和分散图，最后一节提供了对核心结构的额外分析2. 复杂性和二分性的约定图我们从上一节中形式化了“描述”和“Kolmogorov复杂性”的概念，回顾了条件复杂性的定义，然后讨论了二分图。在整个手稿中，x表示字符串x的长度，S表示集合S的基数。对于每一台图灵机M，我们称之为C M（x）= min {|p|：M（p）= x}关于M的（普通）Kolmogorov复杂度。设M0，M1，.。。是所有图灵机的有效枚举。让 、表示其输出具有长度的字符串对的多项式时间可计算编码，该长度是以下的线性函数：短时间内最短描述的短列表3⟨⟩⟨·⟩ |⊆×⟨||⟩第一坐标这个标准机器U具有这样的性质：对于任何进一步的机器M，存在一个常数d使得对于所有字符串x，CU（x）≤CM（x）+d，详情见[5]。对于本文的其余部分，让C=CU表示标准机器U的柯尔莫哥洛夫复杂度。如果U（p）=x，我们就说p是二进制字符串x的描述。在讨论对时，我们可以省略分隔符为了可读性。给定b的条件复杂度，或C（a b），是将字符串b转换为字符串a的最短字符串的长度。更具体地说，C（a）|b）= min {|p|：U（p，b）= a}。我们将使用下面的符号表示图。三 元 组（L，R，E）表示二部图，其中L是左顶点集，R是右顶点集，E LR是一组连接这两半的边缘。对于任意一组顶点S，E（S）表示S的邻居，一个二分图的左度为d，如果它的每个左顶点在R中恰好有d个邻居。一个二部图族称为显式图，如果对于每个左度为d的成员（L，R，E），L中任何顶点的第i个邻居都可以在log L，logd中用时间多项式计算。当家族背景清楚时，我们简单地说（L，R，E）本身是显式的。类似地，如果每个左顶点x的第i个邻居可以在时间poly（|X|，日志|E（{x}）|）.3. 先前和相关结果Buhrman，Fortnow，Laplante[3]和Muchnik[6]观察到，如果一个哈希值在一类字符串中或多或少地确定了一个字符串，那么该哈希值就可以作为该字符串模建议的描述。虽然[3]的作者使用随机性提取来获得Kol- mogorov复杂性的多项式时间变量的界限1，[6]采用概率方法来证明[1] Bauwens、Makhlin、Vereshchagin和Zimand [1]改进了[3]中的可区分复杂性结果。4杰森·托伊奇|| |||一个类似膨胀器的物体的存在后者转化为下一个关于条件复杂性的陈述。MUCHNIK的连续性复杂性定理（6）。 对于n个字符串x和y，存在一个字符串p，使得(i) C（x）|时间复杂度O（log）|X|）的情况下，(ii) |= C（x| y），以及|y), and(iii) C（p|时间复杂度O（log）|X|）的。隐藏常数不依赖于x、y或p。Muchnik假设Alice想要发送一个字符串x给Bob，而Bob已经知道y。根据定义，Alice必须发送长度至少为C（x y）比特的消息p给Bob，以便与x进行通信。Muchnik根据该定理，Alice需要对数建议来编码消息p，Bob则只需要对数建议来将p转换回x。Musatov、Romashchenko和Shen最近的一篇论文[8]给出了Muchnik条件复杂性定理的两个组合证明。第一个证明引入了在线匹配（定义6），大致遵循了Muchnik[6]而第二个呼吁随机提取沿线Buhrman，Fortnow，和Laplante[3]。我们的主要结果的证明，推论8，在其核心结构中结合了这两种方法。有些出乎意料的是，我们也可以通过描述列表来理解Muchnik的条件复杂性定理，这是本文的主要对象。我们将在推论9中探讨这种联系的细节。在 [8] 的 基 础 上 ， Bauwens ， Makhlin ， Vereshc hagin 和Zimand[1]以两种方式改进了下面的定理。T HEOREM 1 （ Bauwens ， Makhlin ， Vereshchagin ， and Zimand[1]）. 存在一个可计算函数，它将每个二进制字符串x映射到一个poly（x）大小的列表，该列表包含x的长度C（x）+O（log x）描述。短时间内最短描述的短列表5| || || |- | |他们表明，要么可以在多项式时间内生成列表，要么可以限制所包含描述的长度C（x）+O（1）在后一种情况下，列表的长度可以是x的二次方，而且没有可计算函数可以生成一个更短的列表来描述这种大小[1]。本文还改进了Muchnik的条件复杂性定理。它们表明，在给定O（log x）位的建议的情况下，可以从x有效地计算（iii）中的描述p，并且我们将在推论9中通过证明（i）中的建议位数可以从O（log x）减少到O（ 1 ） 来 进 一 步 改 进 他 们 的 结 果 。 类 似 地 ， Musatov 和Romashchenko[ 7，8]在空间复杂性的背景下研究了Muchnik本文将证明文[1]中定理1的两个改进可以同时实现 我们将有效地生成一个多项式长度的列表，其中包含的描述的长度是在一个加法常数的最佳（推论8）。我们在这里不研究描述的运行时间，但是这些对象的时间复杂度仍然是一个相关的考虑因素。4. 随机抽取工具我们的主要构造结合了分散器和扩展器图，我们从Ta-Shma，Umans和Zuckerman [9]的显式图对象中导出。定义2. 一个二部图（L，R，E）称为（K，E）-分散子，如果L的每个基数至少为K的子集在R中至少有（1 <$）R个不同的邻居.定义3.二部图（L，R，E）称为（K，c）-扩张图如果对于每个大小至多为K的集合SL，|英（西）|≥ c|S|。扩张图和扩散图都是二部图，它们的左侧顶点在右侧有许多邻居，但是它们在两个重要方面不同。首先，扩展器图仅对足够小的集合实现扩展，而分散器图仅对大集合保证分散。其次，扩张器和分散器都涉及左度小的图，6杰森·托伊奇≥◦| || |左手子集有许多邻居，它们在实现这些参数的方法上不同。在二分扩展图中，左手顶点的子集相对于它们的大小具有许多右手邻居，而在扩散图中，左手子集的邻居覆盖整个右手边的大部分T HEOREM4（Ta-Shma，Umans，Zuckerman [9]）. 存在一个常数c> 0，使得对每个K 0，k> 0和任意非空顶点集L，存在一个左次数d=polylog的显式（K，k）-分散子（L，R，E|L|和CKD原木3|L|≤|R| ≤ Kd。Ta-Shma、Umans和ZuckermanDISPERSER LEMMA（Zimand）. 对任意k≥0和任意集合L与|L|≥ 2k，存在显式二部图（L，R，E）◦ 与|R|= 2 k+1，其左次数是logL中的多项式，并且不依赖于k，并且使得L的大小至少为2k的任何子集在R中至少有2k个邻居。P屋顶。 设k ≥ 0，L是一个大小至少为2k的集合. 适用定理4，其中L，K=2k，λ= 1/ 3，并将结果图G=（L，R，E）. G接近于我们需要的，但是右边的顶点集可能太大或太小。如果R= 2k+1，在这种情况下，我们说R具有正确的大小，那么G已经是我们所需要的，因为大小至少为2k的L的任何子集在R中至少有（2/ 3）2k+1> 2k个邻居。考虑R太小的情况，即小于两倍正确的大小（但不等于它）。在这一步中，我们将R的大小过冲一点，然后我们在下一段中对此进行纠正。我们通过合并G的克隆拷贝来增加右手集的大小。形成一个新的图，具有相同的左手短时间内最短描述的短列表7≤−| || |∈ ∈∈-||||≤ ||≥顶点为G，其右手顶点是R与自身的不交并，并且其边与G在每一半上的边相同。该操作使右侧顶点集的大小和图的度都加倍，同时保持分散器参数K= 2k和k= 1/ 3。我们重复这个操作，直到右边的顶点集至少变成正确大小的两倍。得到的图保留了分散器参数，并且度仍然是polylogL，因为定理4为我们提供了一个图，其右手基数已经不小于O（1/ log3L）乘以正确的大小。在不失一般性的情况下，假设R至少是正确大小的两倍。我们把R分成2k+1个大小近似相等的等价类，并把这个类的集合称为RJ。具体地说，我们将R的顶点均匀地分布在类中，使得没有一个类比任何其他类大一个以上的成员。现在定义一个二部图GJ，其左顶点集L，右顶点集RJ，其中xL是y的邻居R Jiff（x，z）E的y的等价类中的某个z我们声称，GJ具有所需的性质的引理。RJ已经是正确的大小，并且刚才描述的折叠操作并没有增加左度数，因此仍然需要验证分散器属性。请注意，每个等价类必须包含至少两个顶点，因为R至少是 正 确 大 小 的 两 倍 。设 t2 是 唯 一 整 数 ，不R/2k+1 |S|。|.Q5. 显式在线匹配现在我们给出主要定理。我们的建设的核心是下面的如果短时间内最短描述的短列表9≥不需要显式图，具有随机选择边的二分图以非零概率2[1]实现引理5的其他性质。第五章. 对每个k 0，存在一个显式二部图（L，R，E），使得◦ L由长度至少为 k的所有二进制字符串组成，◦ R的基数是2k+1，◦ 每个顶点x ∈ L的度是poly（|X|），以及其中L的任何大小至少为2k的子集至少有2k邻居R。多项式Poly（|X|不依赖于k。P屋顶。我们的建设分两个阶段进行。 首先利用扩展引理扩展左边节点L穿过小的中间顶点集M。接下来，我们通过分散引理将相邻点M的扩展映射到一个更小的集合，即右手顶点R。我们所期望的图的边E将由L和R中由这两个映射的合成连接的我们现在讨论如何处理不同长度的字符串L中长度大于2k的每个字符串在R中将有2k个邻居（这是多项式）。对于其余范围k≤n≤2k中的每个长度n，我们在长度n的字符串和中间集合Mn之间创建一个显式二分扩张器，然后将Mn的设L与该引理的假设相同，设k≥0，设Ln表示长度为n的字符串。对于任意的字符串长度k≤n≤2k，我们生成一个显式扩展图Gn=（Ln，Mn，An）.应用Expander引理得到左二部图Gn[2]另见[8]中使用概率方法构造的类似但有限的图的例子◦10杰森·托伊奇Σ| |||图. Expander Lemma组成 与 的 这... Perser引理度Poly（n）和右顶点基数2k+3，它是一个（2k，1）-扩张器. 设M是Mk，Mk+1，. 。。 ，M2k，并且令A表示该嵌入的对应边。也就是说，A={（x，y）：x ∈ L，y ∈ M，且（x，y）∈ An，其中n是任意的}.现在（L，M，A）是一个二部图，其中每个长度为n的字符串的左度是poly（n），并且2K2 K<|M|为|M n|<2k·2k+3。n=k利用Disperser引理，存在一个显式二部图（M，R，B），它的左度数poly（logM）是关于k的多项式，它的右顶点集满足R=2k+1，并且使得M的任何大小至少为2k的子集在R中至少有2k个邻居.最后，设E由L和R之间所有连通的边组成短时间内最短描述的短列表11|| ≥Σ≤通过边集A和B的合成。也就是说，E={（x，y）：x∈L，y∈R，存在z∈M使得（x，z）∈A且（z，y）∈B}。这就得出了二部图（L，R，E）的构造，其对于每个长度为n的字符串的左度不超过时间复杂度：O（n）|M|）}= poly（n），不管n是否> 2 k。设S是大小至少为2k的子集L。如果S包含字符串的长度大于2k，则该串在R中有2k个邻居，所以在这种情况下，我们立即满足E（S）2k。因此，我们可以假设S中的所有字符串的长度最多为2k。从（L，M，A）的展开性质可以得出：2K|为|A n（{ x ∈ S：|X|= n }）|≥2 k，| ≥ 2 k,n=k从（M，R，B）的分散器性质，我们得到|为|B [ A（S）] |≥ 2| ≥ 2如所期望的。Q下 一 个 定 义 和 下 一 个 证 明 中 的 论 点 是 由 Musatov ，Romashchenko和Shen[8]提出的，但为了清晰和完整，我们将它们包括在这里。定义6. 我们说一个二分图（L，R，E）允许最大为s的在线匹配，如果存在一个算法，使得对于L中任意一组大小为s的顶点，其顶点每次被（反向）呈现给算法，算法可以将每个顶点按接收顺序分配给它的一个邻居（不知道接下来会发生什么），并且所有s个元素之后的总分配是一个双射。在线匹配是有效的，如果一个邻居可以选择在时间上线性的输入的程度的对数。我们将使用下面的组合定理来得到我们关于Kolmogorov复杂性的主要结果。K12杰森·托伊奇SS≤·∈i=−1i=0时显式的O线匹配定理。 对于每个k≥0，有存在一个显式二部图G=（L，R，E）使得◦ L由长度至少为 k的所有二进制字符串组成，◦ R的基数小于2k+1，◦ 每个顶点x ∈ L的度是poly（|X|），以及◦ G承认有效的在线匹配到大小2K。多项式Poly（|X|不依赖于k。P屋顶。 设L与假设相同，且k ≥ 0。适用引理5得到，对于每个整数0<一个二部图（L，R i，E i）其中R i是基数为2 i+1的顶点集合，左次数是串长度的多项式，并且L的任何大小至少为2 i的子集在R i中至少有2 i个邻居。此外，设（L，R-1，E-1）是一个二部图，它有一个右顶点是L中每个元素的邻居。我们建立了Ri的设R=i≥−1Ri且E=i≥−1Ei。我们认为外显二部图（L，R，E）具有成立定理所需的性质.由于x∈L中每个顶点的次数是x在所有Ri上的此外，委员会认为，k−1k|= Σ|Ri|i = 2 k +1 − 1。|= Σ2 i= 2 k+1− 1.有效的在线匹配性能有待验证。我们使用贪婪算法。最初，R中的所有顶点都标记为未使用。当一个顶点x∈L进来时，我们将它分配给一个任意的未使用的邻居Rk−1，如果这样的邻居存在的话。如果不是，我们尝试将x分配给Rk−2中未使用的邻居。 如果这是当（如果）x被分配给一个特定的y Ri时，我们将y标记为已使用，并等待L中的下一个顶点到达。连续到达的处理类似。短时间内最短描述的短列表13≥−−−−−| |我们声称每个x都是通过这种方法赋值的，并且由于每个x都被赋值给一个未使用的顶点，因此得到的匹配将是一个双射。我们通过归纳证明了对于任意i≥0，L中不超过2个i顶点在水平Ri上不能赋值假设在水平Rk−1超过了这个界限，让XL表示在这个水平赋值失败的顶点。然后|X|> 2 k−1，因此根据分散器性质|E k−1（X）|≥ 2 k−1。必须使用Ek−1（X）的每个元素，否则我们可以将X的一个元素匹配到它。因此，在Rk−1层匹配或失败的顶点总数超过2k，这是一个矛盾。因此至多有2k−1个顶点在Rk−1层赋值失败，其中至多有一半在Rk−2层赋值失败，因此通过归纳，至多有20个顶点在所有层Ri（i0）赋值失败如果需要的话，R1中剩下的顶点被用来辅助这个顶点.因此，所有顶点都匹配。QR EMARK7（Makhlin）. 在显式在线匹配定理中，R的基数不能减少到2 k，因为在线匹配性质将迫使每个长度为n的右顶点有超过2 n2k个邻居，这意味着限制为长度为n的字符串的图有超过2 k（2 n2k）条边，因此一些长度为n的左顶点的度大于2 k（1 2 k/2 n）。 因此，对于每个k，在L中存在一个长度为n = k +1的串，其度数超过2 k−1。另一方面，对于任何yδ>0，我们可以计算|X|，我们给这个集合添加一个额外的描述，即Mi，xx，其中M i是所有字符串上的恒等映射。Q有人可能会想知道是否有必要添加O（1）误差项。答案取决于底层的标准机器，如[1]所示。虽然存在一个标准的机器，其推论8成立，O（1）等于零，但也有标准的机器。短时间内最短描述的短列表15| || ||⟨ ⟩ ⟨⟩如果O（1）等于0，则列表大小将在|X|。作为进一步的推论，我们改进Muchnik我们定义一个字符串a相对于一个字符串b的时间有界条件复杂度Ct如下：C t（a |b）= min {|p|：U（p，b）在至多t步内收敛到a}。推论9。对于任何字符串x和y，都存在字符串p使得（I）C（x）|时间复杂度O（1）(ii) |= C（x| y），以及|y), and(iii) C聚（|X|）（p|时间复杂度O（log）|X|）的。隐藏常数不依赖于x、y或p。P屋顶。 首先，注意推 论 8 的证明可以很容易地适应条件复杂性：如果我们在所有亲，g p，y而不是p上，并且用p，y而不是p执行计算，则相同的构造有效地计算包含长度为C（x，y）+O（1）的字符串q的poly（x）大小的列表f（x），该字符串q满足U（q，y）= x。假设p是字符串q，其中最后一个位被删除。然后，如果x =0，y= 0，那么就可以用O（1）位的建议来重建x，|p|= C（x|y），以及Cpoly（|X|）（p|x）≤Cpol y（|X|）（q|时间复杂度O（log）|X|）因为O（log x）位足以区分f（x）的成员。Q16杰森·托伊奇| |≤≤6. 多项式有多大在推论8中，我们估计多项式大小列表的大小为3。我们的分析涉及到对结构的一些小修改。在下面的讨论中，δ表示任意的正常数，n是logL的简写。首先，我们在我们的主要构造中计算扩展图的左度，引理5。为了做到这一点，我们必须首先确定定理4中的Ta-Shma，Umans，Zuckerman分散子的左次数。[9]的作者将左次数定义为poly（n），但实际上它不需要超过O（n3）。这个更清晰的界限是通过重做[9，引理6.4]中的复合结构，使用[4，引理4.21]中的提取器。更详细地说，我们从[4，引理4.21]导入参数如下：t（n，k）= log n + O [log k·log（k/k）]，且k = 2 log（1/k）− O（1）。[9，引理6.4]中E1和E2的定义相对于这些变化保持不变，分散子E的计算也是如此。将这个新的E代入[9，引理6.5]，在定理4中产生O（n2+δ）的左次数。 这反过来又给了分散引理中的图一个O（n3）的左度，因为在R的基数小于右大小的情况下，左度可能会稍微增加。通过类似的检查，我们得到了O（n4）的界限， 在扩展引理中，图的左度是O（n2 +δ），但是我们可以通过将该引理替换为以下翼来将其降低到O（n2 +δ）。替代的膨胀器构造。T HEOREM 10（Guruswami，Umans，Vadhan 4）. 存在一个常数c，使得对每个 α，ε>0和每个 0k n，存在一个显式二部图（L，R，E），◦ |= 2 n，|= 2 n,◦ 左次数d=c（nk/n）1+1/α，以及◦ |≤ d2·2k（1+ α）|≤ d2· 2 k(1+α)这是一个[2 k，（1 − k）d]-扩展器。3Zimand[10]改进了度界为6+δ。短时间内最短描述的短列表17≥| |≥≤ ||| |· ||Guruswami、Umans和Vadhan扩展器图实现了到足够小以保持引理5的其他参数的空间中的几乎完美的扩展。 由于引理5中的每个左手顶点x的邻居现在从定理10的扩展图导出，该扩展图与来自本节的修改的分散引理图组成，因此我们计算x的度为O（|X|5+δ）。在这一点上，显式在线匹配定理中的克隆过程将一个线性项贡献给O（x5+δ），而推论8中大小为kx的集合上的并集将使总列表大小为O（x7+δ）。 这就完成了我们对下面结果的研究。11. babyBABY 存在一个常数c 1，使得对于每个δ> 0，存在一个非负d和一个多项式时间可计算函数，其中h ich将一个ch二进制字符串x映射到一个大小为cx7+δ的列表，该列表包含x的长度为C（x）+d的描述。列表大小界限也细化了推论9的第三部分。12. babyBABY存在一个常数c0使得对于每个δ>0，存在一个非负d使得对于任意字符串 x和y，存在一个字符串 p使得(i) C（x）|p，y）= d，(ii) |= C（x| y），以及|y), and(iii) C聚（|X|）（p|x）≤（7 + δ）·log |X|+ c。确认作者感谢Marius Zimand的观察，分散引理，它将推论8中的误差项从O [log C（x）]改进为O（1），并简化了主要结构引理5的证明。还要感谢匿名的裁判指出扩展引理是由Ta-Shma、Umans和Zuckerman的扩散图得出的（定理4），这意味着我们在主要构造中不需要求助于Guruswami、Umans和Vadhan扩展图（定理10）18杰森·托伊奇引用[1] Bruno Bauwens，Anton Makhlin，Nikolay Vereshchagin，and Marius Zimand.在短时间内用短节目短名单。IEEEConference on Computational Complexity（CCC），第98-108页， 2 0 1 3 年 6 月 。[2] 理查德·贝格尔、哈里·布尔曼、彼得·费耶尔、兰斯·福特-诺·W、彼得·格拉·博维斯基、吕克·朗普·雷、安德烈·穆·奇尼克、弗兰克·斯蒂芬和莱恩·托伦弗利特。Kol- mogorov函 数 的 枚 举 。 The Journal of Symbolic Logic ， 71（2）：501 - 528，2006.[3] 哈里·布尔曼，兰斯·福特诺，索菲·拉普兰特。资源受限Kolmogorov 复 杂 性 的 重 新 审 视 。 SIAM Journal onComputing，31（3）：887[4] Venkatesan Guruswami ， Christopher Umans ， and SalilVad- han. Parvaresh-Vardy码的不平衡扩展器和随机性提取器。Journal of the ACM，56（4）：20：1[5] 李明和保罗. Kolmogorov复杂性及其应用计算机科学中的文本Springer，纽约，第三版，2008年。[6] 安德烈·A穆奇尼克条件复杂度和代码。理论计算机科学，271（1-2）：97[7] 丹尼尔·穆萨托夫通过“朴素”去随机化改进Muchnik条件复杂性定理的空间有界版本。在计算机科学-理论与应用中，计算机科学讲义第6651卷，第64- 66页。76. Springer Berlin Heidelberg，2011.[8] Daniil Musatov，Andrei Romashchenko，and Alexander Shen.Muchnik条件复杂性定理的变体。计算系统理论，49：227短时间内最短描述的短列表19[9] AmnonTa-Shma ， ChristopherUmans ， andDavidZuckerman. 无 损 冷 凝 器 、 不 平 衡 膨 胀 器 和 萃 取 器 。Combinatorica，27：213[10] 马里斯·齐曼德在短时间内短节目短名单-一个简短的证明，2013年。曼恩角http://arxiv.org/pdf/1302.1109.pdf。[11] A. K. Zvonkin和L. A.莱文有限对象的复杂性以及通过算法理论 发 展 信 息 和 随 机 性 概 念 。 Russian MathematicalSurvey，25（6）：832013年1月3日收到Mandarin pt杰森·特伊奇宾夕法尼亚州立大学