随机结构的复杂性的一阶逻辑深度与随机图的逻辑深度的比较研究

22理论计算机科学电子笔记143（2006）197-206www.elsevier.com/locate/entcs随机有序结构的复杂性乔尔·H Spencer斯宾塞1，2纽约大学柯朗学院251 Mercer StreetNew York，NY10012Katherine St. John凯瑟琳·圣约翰1，3雷曼大学数学系计算机科学研究生院纽约城市大学Bronx，NY10468摘要我们证明了对于随机比特串Up（n），概率p=1，区分非同构结构所需的一阶量化器深度D（Up（n））是Θ（lg lg n），概率很高。进一步，我们以很高的概率证明了：对于随机序图，G≤，p（n）有边概率p = 1，D（G≤，p（n））= Θ（logn），与Kim等人[ 5 ]关于随机（无序）图Gp（n）的结果D（Gp（n））= log1/pn+O（lglgn）形成对比.关键词：随机图，随机位串，一阶逻辑，Escherichfeucht-Fraisse游戏1我们感谢裁判的有益的意见。第二位作者感谢NSF ITR 01-21651和MRI 02-15942的支持以及Bar cel o n a，Span in的Centre deRecercaM ate m`atica的热情好客。2 电子邮件地址：spencer@cs.nyu.edu3电子邮件：stjohn@lehman.cuny.edu1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.05.030198J.H. Spencer，K.圣John/Electronic Notes in Theoretical Computer Science 143（2006）1971引言有几种自然的方法可以测量结构的复杂性：使用的变量的数量，句子的长度和量化器的“深度”。我们将重点关注最后一个衡量标准--句子中量化器嵌套的深度或数量。句子的quantier深度对应于将句子作为程序实现所需的寄存器数量，也对应于Escherichfeucht-Fraisse游戏中的移动数量[9]。在[5]之后，我们定义D（φ）为一阶句子φ的quantier深度，D（G）为定义有限结构G的句子的最小深度。Kim等人 [5]探索了随机（无序）图Gp（n）的D（G p（n）），并表明对于常数p，D（Gp（n））=O（logn），具有很高的概率，并且对于精心选择的（非常数）p值，D（Gp（n））可以是Θ（logn）。随机图的一阶复杂性也被研究的收敛规律。Fagin和也就是说，对于每一个第一阶句子φ，limG p（n）|= φ = 0或1n→∞Shelah和Spencer [8]表明，对于边缘概率p=n−α，0<α 1，收敛依赖于α的值。对于有理数α，存在一个0 - 1定律，但对于无理数α，存在一阶句子，上面的极限不收敛。许多更强的逻辑在随机结构上已经被探索过（参见[2，9]的例子）。另一种增加表达能力的自然方法是在签名中添加一个排序（参见[9]的第11章）。在本文中，我们专注于两类这样的结构：有序随机图和随机位串。令人惊讶的是，对于随机图，我们证明了序不仅给出了D（G≤，p）对一个C（tp）的一个非常小的值，具有很高的概率，而且给出了可能的最低界。也就是说，区分具有高概率的随机有序图所需的量化深度为D（G≤，p）=Θ（lo gn）。我们还研究了有序结构的自然类，即随机位串（也称为随机有序一元谓词）。零-一定律也被证明是随机位串[1，6]。Spencer和St. John [10]研究了0 - 1定律的收敛速度，并定义了一类结构的韧性，以通过一阶逻辑来捕捉相似性。在一般设置（定义为所有n的随机结构）中，坚韧度函数T（n）等于最大k，因此如果n1，n2≥n，则复制者赢得这个k步Escherichfeucht-Fraisse博弈（在§2J.H. Spencer，K.圣John/Electronic Notes in Theoretical Computer Science 143（2006）1971992下面）在大小为n1和n2的独立结构上进行，概率至少为1−1。 斯宾塞和圣约翰给出了韧性函数，用于概率p的几个非常数选择。韧性与测度D密切相关。我们证明了区分概率为p=1的随机比特串所需的量化深度D（Up）的紧界。即，D（Up）= Θ（lg lgn）。在第2节中，我们给出了一些背景和回顾过去的工作。第3节包含随机位串的结果。第4节包含随机有序图的结果。最后，我们与开放的问题和未来的工作。2背景本节包含博弈和概率的背景信息。专家不妨跳过前两节，集中讨论最后几节的定义。有关一阶逻辑的详细信息，请参阅[3]以获得出色的概述。关于博弈、概率和逻辑的更全面的讨论，见[9]。2.1Escherichfeucht-Fraisse博弈这个博弈及其等价性是由Escherichfeucht和Fraisse提出的，这里的介绍来自[9]。在Escherichfeucht-Fraisse游戏中，玩家交替将鹅卵石放置在两个结构中的一个上，作为游戏板。所玩的回合数对应于所考虑的一阶句子的复杂度 给定两个结构，M1和M2，M1和M2是不可区分的由数量级最多为k的一阶句子（写作M1kM2）当且仅当第二个参与者对于在M1和M2上进行的每一个有限步数的k-卵石Escherichfeucht-Fraisse博弈都有获胜策略。我们定义下面的游戏：定义2.1在M1和M2上的k-卵石Escherichfeucht-Fraisse博弈（EF博弈）是一个完全信息的两人博弈。对于游戏，我们有：• 玩家：有两个玩家：· 参与者I，通常被称为破坏者，他试图破坏结构之间的任何对应关系。· 玩家II，通常被称为复制者，他试图复制剧透的最后一个动• 设备：我们有k对鹅卵石和两个结构M1和M2。M2作为游戏板。200J.H. Spencer，K.圣John/Electronic Notes in Theoretical Computer Science 143（2006）197• 移动：玩家轮流移动。 在第i步，剧透选择一个结构，并将他的第i个鹅卵石放在该结构中的一个元素上。然后，复制者将她相应的鹅卵石放在另一个结构中的一个元素上。• 获胜：如果在复制者的任何移动之后，由鹅卵石诱导的子结构不是同构的，那么破坏者获胜。当双方都走了k步后，如果破坏者没有赢，复制者就赢了。2.2随机有序结构在[10]之后，我们定义随机位串或随机一元谓词如下。 签名是σ={U，≤}，其中U是一元谓词，≤是遵循线性序公理的二元谓词。设n为正整数，0≤p（n）≤1。如果字符串中的第i位是“on”，我们将写U（iU是一个一元谓词随机位串U p（n）是谓词U on [n] ={1，.，n}，其概率由Pr[U（x）]=p（n）确定，其中1≤x≤n，且事件U（x）在1≤x≤n上相互独立。[ 9]《易经》中的“道”，是指“道”。签名是σ={σ，≤}，其中σ是表示边的二元谓词，≤是遵循线性顺序公理的二元谓词。设n为正整数，0≤p（n）≤1。如果n i和j之间有一条边，我们就写ij。随机有序图G≤p（n）是n阶有序图上的概率空间由Pr[i<$j] =p（n），对1≤i，j≤n，事件i<$j相互独立且均匀分布。2.3一阶结构我们通过一个一阶句子φ的量化器深度来衡量它的复杂性，它是φ中嵌入的量化器的最长序列。例如，n个顶点上的完全图可以用一阶句子来描述01 - 02-02-02I jx1=x2=x3 = x4（我y=xi）当x和y之间有一条边时我们写 这句话的第一第二部分说至少有n个不同的点。这个句子有数量深度D（φ）=n+ 1。 请注意，任何有限图都可以用一个一阶句子来描述，这个句子可能很大，可以列出每个顶点J.H. Spencer，K.圣John/Electronic Notes in Theoretical Computer Science 143（2006）19720122并根据特定顶点描述存在和不存在的边。通常可以做得比这更好，如上面描述n个顶点上的完全图的句子考虑到这一点，我们专注于D（G），由Pikhurko等人定义。 【7】：D（G）= min {D（φ）|G| = φ&如果H/G则H| = φ}对于任何结构，这个函数的平凡界限是：其中logn = min {i ∈ N |log（i）n <1}。3随机位串我们专注于概率为p=1的随机位串的情况2如2.3节所述，我们有一个下界D（G）=（logn). 我们可以通过关于随机比特串中的字的出现的直接变元将其改进为lg lgn引理3.1如果y是x的子串，则D（y）≤ D（x）。证明：如果y是x的子串，那么它可以写成x=pys，其中p（prefix）和s（su_x）是一些二进制字符串。 如果D（y）=k，则存在另一个yJ所以复制者在y，y，J上赢得k-但是复制者在pys，pyJs上赢得k-1步博弈，只要破坏者在prefix或sufix中使用相同的策略因此D（x）≥k。Q我们使用这个引理来证明我们的第一个定理--比特串的量化器深度的下界。证明的思想是，如果一个长度为n的比特串U包含一个特定的子串，例如0L，另一个比特串UJ包含稍微不同的子串，例如0L+1，那么Spoiler至少需要10（lgL）步才能区分这两个结构。当L=lgn时，长度为L的单词出现的概率很高，因此，至少需要Spoiler用ε（lgL）= ε（lg lgn）来区分结构。这对应于下面定理中的下界D（Up（n））= n（lg lgn定理3.2对于随机比特串Up（n），其中p=1，D（Up（n））=（lglg n）的概率。证明：有了上面的引理，下界可以从显示(i) 在高概率的情况下，随机n长度比特串包含0L，L=[0. 9lg n.(ii) D（0L）≥lgL。202J.H. Spencer，K.圣John/Electronic Notes in Theoretical Computer Science 143（2006）19722对于第一部分，我们将n长度的位串拆分为[n/L]个长度为L（加上一些多余部分）的不相交每个这样的字符串都是OL，概率为2−L，所以它们都不是0L的概率是（1−2−L）[n/L<$→ 0。对于第二部分，我们需要证明D（0L）≥lgL。为了证明这一点，我们在0L和0L+1上玩Escherichfeucht-Fraisse游戏。由定理2.6.3（[9]的第41页），Duplicator在两个n，m元全序集上的k步博弈有获胜策略当且仅当n=m或m，n≥2k− 1。因此，对于k= lgL，复制者赢得了k步博弈，并且D（U）≥lgL。根据引理，D（U）≥D（0L），因此，D（U）≥lglgn。Q上界更复杂，并且依赖于以下事实：适当选择L，长度为L的每个字符串最多出现一次。长度为L的弦的唯一性使我们能够在更小的量子深度上描述其结构。定理3.3对于随机比特串，其中p=1，D（Up（n））=时间复杂度为O（log n）证明：证明依赖于三个部分：(i) 对于任何L，长度为L的每个字符串s都可以用lgL量化深度来描述。(ii) 其中，L =[2。1 lgn，很有可能不出现长度为L的字符串不止一次(iii) 通过第（1）和（2）部分，我们可以用适当小的量化深度来描述结构请注意，第一部分是简单的，因为任何长度为n的位串都可以用一个量子深度为lgn的句子来完全描述。 这个想法是遵循一种对于第二部分，我们让L =[2。1 lgn，并表明长度为L的字符串不会出现超过一次。对于一个固定的L，长度为L的字符串s出现两次的期望个数为≤（n-L）（n-L-1）（1/2）L。如果L =[2. 1 lgn，出现两次的字符串的期望数量以很高的概率变为零对于最后一部分，我们需要以高概率在O（lg lgn）中完全描述 Up（n）。由于每个长度为L的字符串最多出现一次，概率很高，我们可以将结构的描述简化为描述长度为L的字符串出现的顺序。如上所述，描述长度为L的单个字符串需要O（lgL）的量化器深度。为了描述两个连续出现的字符串，长度为L的s和t需要O（lgL）。这可以通过定义一个谓词NEXT来实现，使得：下一个[S，T]：x（J.H. Spencer，K.圣John/Electronic Notes in Theoretical Computer Science 143（2006）197203K和谓词INIT：INIT[S]：（给定起始位置x，需要[lgL] + 2个quantier深度来描述NEXT的每个子句。INIT也可以用[lgL] + 2量化器深度来描述。对于2个L对（S，T）中的每一个，我们将有NEXT[S，T]或<$NEXT[S，T]。这与非重复性相结合，决定了SE-顺序。再次使用“分而治之”的因此，D（Up）=O（lgL）=O（lg lgn），具有很高的概率。Q4随机有序图对于随机有序图，我们对任何结构都有一般的logn的下界（见2.3节）。我们表明，上界匹配的最佳可能的下限。要证明上界是复杂的，并且依赖于定义给定结构G的句子大小的递归参数。为了证明的清晰性，我们将逻辑和概率结果分开。首先，我们给出一个一般的界，如果一个图G满足一些邻接条件（在下面的定理4.1中列出），那么D（G）可以从上面很好地有界。然后，我们证明了n个顶点的随机有序图G≤p（n），通过递归地应用定理4.1，可以证明这是一个非常简单的过程，并且可以达到O（log n）的上界。定理4.1设a0 aJ再走一步就赢扰流板然后选1，a k−1，复制器的响应是aJ，.，aJ. 为1k−1xJ∈GJ，其中x∈[aJ，aJ），1≤i≤k，设PROJ [xJ]，xJ的轮廓，表示与xJ相邻的y aJ的集合。设GJ有一个i，0≤ik，且yj不同，ZJ∈[AJ，AJ）与i i+1PRO[yJ] = PRO[zJ]。 Spoiler然后会选择yJ，zJ∈GJ和Duplicator需要在G中选择不同的y，z∈[ai，ai+1）。我们关于G的假设确保PRO[y]/=PRO[z]。然后Spoiler将选择x∈G，其中x∈[0，ai），使得y，z中恰好有一个与x相邻，并且Duplicator将具有没有反应。我们把上述阶段称为初始阶段。它最多持续0+k+3步。让我们假设复制者还没有输，并将剩下的移动称为最后阶段。我们首先得到了0≤i≤k的一个辅助结果。COPY[i]：SupposeG|[0，a）GJ|[0，aJ）且x∈G，xJ∈GJ有hxxJ且我我进一步假设最后阶段的第一轮由移动x，xJ组成。然后剧透可以在最后阶段以（最多）i+1步的总（包括第一轮）获胜。对于i= 0，没有什么可显示的。假设COPY[i−1]，并令x，xJ满足COPY[i]的假设。如果x，xJi.所以PRO[x]/= PRO[xJ]。Spoiler在集合的对称差中选择y ai−1Duplicator不能选择相同的y，因此必须选择yJ 0时，ta0=10 gn，ai+1=[2ai/4]。 我们的目标是k=O（logn），其中a k= n。这给出D（G）= 2O（logn）+4+logn =O（logn）。为了说明这一点，我们引入了一些命题：设b0=10 gn，且dbi+1=2bi，其中i > 0。注意，对于l=logn，bl= Tower（logn）=n。通过归纳法（以及一些繁琐的技术细节），a4i≥bi，其中i>0。这给出a4l≥bl=n。所以，k= Θ（l）=Θ（logn）。接下来，我们需要证明区间（ai，ai+1）在[1，ai]中具有唯一的轮廓。假设没有。对于特定i，失败的概率小于（ai+1−ai）22−ai，其中hichisbounderdabovebya2·2−ai. Sincea=[2ai/4ai，2i+1i+1这是一个2−ai/2的数。完全失败的可能性不大i2−ai/2≤j≥a0 2−j/2=O（2−ai/2）=o（1）a0goestooinfinitey. 我公司生产的产品如果满足定理3，我们就得到了想要的结果。Q5结论和今后的工作我们展示了区分两类自然随机有序结构所需的量化器深度的紧界：位串和图。我们的工作集中在具有恒定概率p=1的随机结构上。相关的开放性问题包括其他随机有序结构的复杂性，比特串和具有非常数概率的图的复杂性。引用[1] Dolan，P.，A zero-one law for a random subset，Random Structures and Algorithms 2（1991），pp. 317-326206J.H. Spencer，K.圣John/Electronic Notes in Theoretical Computer Science 143（2006）197[2] Ebbinghaus，H. D.和J. Flum，[3] 恩德顿，H. B、“A Mathematical Introduction to Logic,” Academic Press, San Diego,[4] 费金河，广义一阶谱和多项式时间可识别集，在：计算的复杂性，SIAM-AMS会议记录，1974年，pp.43比73[5] 金，J.H、O. Pikhurko，J.Spencer和O.Verbitsky在《How Complex Are Random Graphs inFirst Order Logic？（2005），出现在随机结构和算法。[6] 林奇， J.F. ， Probability of first-order sentences about unary functions ，Transactions of theAmerican Mathematics Society 287（1985）. 543-568[7] Pikhurko，O.，H. Veith和O. Verbitsky，The first order definability of graphs：Upper boundsfor quantier ranks（2003）。电子版arXiv：math.LO/0305244。[8] Shelah，S.和J. H. Spencer，稀疏随机图的零一定律，美国数学杂志1（1988），pp. 95比102[9] 斯宾塞，J.H.，“The Strange Logic of Random Graphs,” Springer, Berlin,[10] 斯 宾 塞 ， J.H. 和 K. St. John ， The tenacity of zero-one laws ， The Electronic Journal ofCombinatorics 8（2001），p. R17[11] Y. Glebski，M.，D. Kogan和V. Talanov，限制谓词演算中公式的可实现性范围和程度，Kibernetica 2（1969），pp.17-