建议类和复杂性关系:Kannan定理变体和电路规模层次

不||∀| ⟩ ∈|⟩ ∈⊆⊆CFF→ ∈ F∈ CK针对建议类克里斯·波利特抽象。给出了Kannan定理的变体，其中原定理的电路被使用建议字符串并满足某些温和条件的任意递归可表示语言类所取代。时间复杂度为O（nk）。这些变种，王空军假设DTIME（nkJ）NE/polyk不包含PNE，DTIME（2n）/poly不含EXP，SPACE（nkj）/polyk不含PSPACE，uniform TC0/polyk不含CH，uniform ACC/polyk不含ModPH。选择集的后果也得到了。特别地，证明了RDTIME（nk）（NP_sel）不包含在PNE中，RDTIME（nk）（P-sel）d不包含EXP，且RDTIME（nk）（L-sel）dT T不包含PSPACE。最后，建立了电路规模层次定理.关键词建议类，EXP，NEXP，NE，CH，ModPH，p-选择性主题分类。类别和主题描述符：F.1.3 [计算理论]：复杂性类之间的关系1. 介绍描述非一致复杂性类的一种方法是用建议函数。 集合A在/，其中是从N到N，如果有h：Naf和一个B使得对于所有n，我们有h（n）=f（n），并且我们有x = f，x A当且仅当x，h（x）B。具有多项式大小电路的语言可以被表征为P/poly，其中poly是从N到N的多项式有界函数类，并且具有p大小分支程序的函数类为L/poly。尽管多年的研究，它是开放的，无论是NEXP P/聚，甚至NEXPL/聚乙烯。在本文中，建议字符串特征的非均匀类，而不是他们的组合特征更详细地审查，试图既简化现有的证明，以及摆脱一些洞察力，这些困难的问题。本工作的起点是Kannan（15），它展示了NEXPNP中需要超多项式大小电路的集合。Kannan还提供了2不C F/200cCCFCC中、法/英不联系我们K在不经意间对于任何固定的k，要求电路的大小大于nk。这个想法这些结果是猜测一个稍微大一点的最小电路，并验证没有更小的电路可以计算它。2这种更大尺寸的电路可以工作，下面是一个计数参数。这个计数参数是针对特定的计算模型完成的，所以如果想要将这个结果转移到其他模型，就必须提出一个新的计数参数。另一种方法是通过Komolgorov复杂性来计算非一致类的下界使用这种方法，Homer和Mocas（14）证明了EXP DTIME（2O（n1））/nc2，其中c1和c2是固定的。这里建议字符串的长度正好是nc2而不是O（nc2）。Fu（7）也用这种方法证明了EXP不包含在确定性时间nk可约为p-选择集的集合中。这里k是固定的，本文使用的符号RDTIME（nk）（P-sel）这一类的集合。这些结果中使用的Komolgorov复杂性概念是基于时间的，因此将它们推广到空间，计数或概率类需要重新处理参数。然而，如果一个非统一类有一个通知特征，那么通知字符串本身既可以用作诊断的组合对象，也可以用作随机的、更大的、硬字符串的来源。本文提出了三种对通知类/对角化有用的语言。使用这些语言，Kannan定理的两个建议版本被证明。 在交替方面，稍微强一点的变体是，/2012-TIME（[t（n）]O（1））CJ其中 o（t（n）），和JARrerecursivelypresentable类的语言，并且J包含类的 证明思想来自于Kannan渡边（5）。本文RDTIME（nk）（L-sel）PSPACE，kJ> 0. 这里的poly是时间复杂度O（n）使非一致复杂性类一致的一种常用技术是要求非一致类中的组合对象的某些属性具有低复杂性。例如，一个电路族{Cn}是DLOGTIME均匀的，如果一个人可以在DLOGTIME在Cn的大小确定是否有两个门在Cn连接，如果是，由什么门类型。不知道TC0，即由非均匀恒定深度阈值电路计算的语言类，是否包含所有的计数层次CH（P，PPP，PPPPP，.. . ）的。然而，从Caussinus等人（6）得知，DLOGTIME均匀TC0，uTC0不包含CH。Allender（1）给出了一个阈值机器对角化证明这一事实的基础上，填充对角化技术中使用的证明联系我们KK非确定性时间层次定理（21; 27）。在本文中，我们展示了我们Kannan定理的一个变体意味着u TC 0 / poly /pitch CH。也就是说，在一些非均匀性被添加回来之后分离这些类。 One还得到类ACC，均匀，恒定深度，无界扇入，AND，OR，MODm门（对于任何m）电路的类，其中nk建议是这里ModPH是多项式时间层次的推广，它允许模块计数量词。这些结果似乎是迄今为止最为人所知的。最近，Vinodchandran（24）表明，PP不包含在大小为nk的电路中，对于任何固定的k。需要指出的这个结果并不直接意味着UTC0/poly/PICCH是类uTC0包含任意多项式次数大小的阈值电路，即使它们是均匀的。另一个应用程序的建议为基础的方法来分离不均匀的类，是使用本文中构建的三个对角化语言之一，从其他建议类的建议字符串较短的建议类分离的可能性使用这个思想，可以显示许多组合类的大小层次结构作为这个思想的一个例子，推论7表明对于有界扇入、AND、OR、NOT电路，SIZE（α（n）s（n）log2s（n））≥SIZE（s（n）），其中α（n）是一个非减无界函数，它是o（s（n））。本文的组织如下：第2节总结了本文中使用第3节介绍了三种可用于对通知类进行对角化的语言它还提供了Kannan（15）的基于建议的变体。第4节研究了通过减少基于建议的类来计算语言的能力。这两个部分的推论，然后给出。第6节考虑了早期结果对选择集的影响。第7节涉及将通知类与其他通知类分开。2. 预赛由 Balc'aza r 、 D'ıaz 和 Gabar r'o （ 2;3 ） 、 Pa padimitri ou （ 1 7 ） 、Hemaspaandra和Ogihara（11）以及Vollmer（25）撰写的书籍对建议类和电路复杂性有更多的了解。本节仅包含以下所需内容。为了方便起见，本文考虑的机器的字母表是0， 1。符号0， 1≤n用于表示长度小于或等于n的超过0，1的字符串。vw和v-w都将用于表示字符串的连接。值 的序列为1，. . . ，xn被定义为通过将xi中的0和1分别替换为00和10而获得的字符串并在数字之间插入01我们经常使用量词，例如⟨⟩⟨⟩| | ≤⟨⟩C CFC{|}∈{}（y0， 1≤n）或（zn）。在第一种情况下，我们将y视为一个字符串，我们通常希望通过非确定性地猜测它的位来实现它;在第二种情况下，我们将z视为一个数字，并打算通过使用计数器和循环值来实现它对于一个数z，使得z i，我们使用符号0 i+ z来表示长度为i的字符串，它由前缀i-1组成。|z|许多零后跟z，写为二进制字符串。在本文中，次线性时间机器以一种稍微不标准的方式运行：输入磁带被视为读写的预言机，我们允许一个操作来快速分解输入序列。 首先，允许有一个主输入带t0和几个辅助输入带t1，. . .，t k.对输入1，. . . .，xk，则机器可以进入特殊状态，并且在一个时间步中，使x1从该元组解码并写入磁带t1，x2从该元组解码并写入磁带t2，等等。为了读取输入带，机器计算工作带上的i，进入指定从哪个带读取tj的查询状态，并且在一个时间步中根据该带的第i个带方格上的符号进入固定的有限状态集合中的一个 对于写入，机器计算一对i，b，其中b ∈（在本文的情况下，={0，1}），进入所需磁带t j的特殊状态，然后b在一个步骤中成为输入磁带t j的第i个符号。如果机器还可以访问另一个oracle集合A，则此操作很有用：机器可以对输入进行更改，然后向A查询输入的更改版本。 对oracle A而不是输入进行查询也有点不标准：t1，. . . 写入T_k，其中T_i现在可以是输入或工作带，并且进入查询状态。 oracle A接收x1，. . . 其中xi是磁带ti的内容。 根据这是否在A中，机器进入适当的状态。 对机器模型的这些改变最多给出比通常模型的线性加速。给定一个谓词A（x），A（x1，. . .，xk）表示A（x1，. . .，x k）。通常，集合A和它的特征函数A（x）之间的区别被掩盖了。C的递归表示是DTM的有效枚举M1，M2，· · ·，其复杂性类P、NP、PP、PSPACE等。都有这样的递归表示。关于这种递归表示的主要结果在Balc′aza r，D′Zhaz和Gabar r′o（2）中给出. 这将是一个假设，每个chlangua ggets 枚 举 无 限 经 常 在 递 归 表 示 。 本 文 的 其 余 部 分 假 设 ：（1） 、J是递归可表示的，（2）是一类从N到N的非减函数，以及（3）t=t（n）是非减函数，C∪∪∪C FN上的时间可构造函数定义1. 设C/f表示形式为{x| 100× 100 × 100 × 100（|X|）<$∈ L}，其中L在C中，h是从N到{0，1}<$的函数，f是从N到N的非减函数，使得对于所有n，|h（n）|= f（n）.给定一个从N到N的非减函数类F，设C/F表示对于F中的某个f，属于C/f的语言类L.作为一个例子，当函数f在上面的定义中是f（n）：= n k时，使用符号/nk。我们将考虑的一些常见的函数类log：={f |f（n）∈ O（log n）}lin：={f|时间复杂度O（n）quadratic：={f|时间复杂度为O（n2）多边形k：={f|时间复杂度为O（nk）最后，poly：=kpolyk。形式为/的类称为通知类。 最有趣的建议类是P/poly和L/poly。这里P表示多项式时间，L表示对数空间。已知P/poly类由p大小电路识别的语言组成，L/poly类由p大小电路识别的语言组成，由p大小的分支程序识别。PRTIME（t（n））表示那些在时间O（t（n））内可由NTM判定的语言， 其中接受条件是当它在 语言中时超过一半的路 径接受。PP 是kPRTIME（nk）。本文使用以下复杂性类的标准名称：E：=DTIME（2行）NE：=NTIME（2直线）EXP：=DTIME（2多边形）NEXP：=NTIME（2多边形）C0PRTIME（t（n））：=DTIME（t（n））Ci+1PRTIME（t（n））：=PRTIME（t（n））CiPRTIME（t（n））CH（t（n））：=iCiPRTIME（t（n））CiP：=CiPRTIME（poly）CH ：=CH（poly）设T_k（T_k）-TIME（t（n））表示那些被任何交替TM识别的语言，最多有k个交替，最外面的是在时间O（t）中运行的存在将DTIME（t（n））写成k-TIME（t（n））k−TIME（t（n））。当时间界限是多项式时，使用较短的符号p、p和pk k kC⟨⟩⟨⟩||≤||在这种情况下，如果一个oracle集合A也在使用中，则bmp（A），bmp（A）和bmp（A）是k k k避免使用下标和上标。最后，co-C表示类{L<$|L∈C}。主要结果需要下一个定义定义2. CJ 对 于 C是泛的 （余泛 的），如果对于C的某个固定枚举， U：={\displaystyle\mathbb {e，x}）|C的枚举中e的语言包含x} ∈ CJ（U∈co-C）.如果它是普适的或余普适的，则CJ是π这个词是为这篇论文发明的，作为一种方便的方式来写全称或共全称。读者可以检查NEXP对于co-NE是共通用的，PSPACE是通用的并且对于L是共通用的。一个集合和它的谓词之间的区别被忽略的常见地方是对于这个全称集合U;符号U（e，x）将经常用于对应于这个集合的谓词。下一条注释说明了如何从一个显示通用性的U到一个C的递归表示。REMARK 1. 注意，如果CJ是递归可表示的，并且C通过谓词U（e，x）可表示，则C是递归可表示的。这是因为在CJ的枚举中的某个点上，必须出现一个用于U的机器MU。这台机器MU停止在其所有的输入。因此，在CJ是通用的情况下，C可以通过列出基于MU的机器Me来表示，其中e的值已经被硬编码。如果J是共泛的，则从这些Me得到表示交换接受和拒绝状态。定义3. 假设|z| ≤ |X i|.类C是可清除的，如果P（x1，. . .，xn）为C中的谓词意味着P（x1，. . . ，0|Xi|+z，. . . ，xn）也是C中的谓词e。要看到类P是可清除的，考虑谓词P（x1，. . . ，xi，.. . ，xn）在P.给定一个输入字符串x1，. . .，xi，. . .，xn，z其中z x我们可以在线性时间内计算t环x1，. . . ，0|Xi|+z，. . . ，xn，然后使用这个字符串计算谓词P。对于次线性时间机器，|Xi|我想我是来找你的。由于我们将多次考虑可以访问oracle的把这个操作“推”到预言机本身，这样次线性时间机器就不需要担心这个操作了。如果我们正在考虑的神谕类是可清除的，那么我们可以在不离开这个类的情况下做到这一点C吉吉我吉吉accM（0 +j，Aux（C，t）i，j−1），其中，M（0i+j，Aux（C，t）i，j−1），otherwise.如果Aux（C，t）i，j=accM（0i+j，Aux（C，t）i，j−1）;我我L（C，t）i，j：=我3. 主要结果现 在探 讨三 种针 对建 议类 进 行对 角化 的方 法。 第 一个技 巧 来 自 于Schéoning对K an nnan（1 5）的结果的推广（2 0），它是这个证明的基本思想是枚举多项式时间机器。阶段i对机器Mi进行对角化，并建议长度小于i的字符串logi。这是在子步骤中完成的，其中第一个是对每个小于此长度的建议字符串在输入0i上运行Mi字符串0i被放入语言中当且仅当大多数情况下Mi拒绝。然后对输入0i +1和在第一子步骤中正确回答的建议字符串重复该过程。再次采用多数至少会使剩余的正确回答建议字符串的数量减半。在ilogi+1个子步骤之后，没有留下正确回答的建议字符串，并且针对Mi的对角化完成。这个论证的思想现在被抽象化了，以便可以得到一个一般性的结果。定义4. 设acc M（x，A）（rej M（x，A））表示字符串y ∈ A的集合使得在输入端x，y上的M接受（分别为 不合格品）。回想一下，我们假设t是N上的非减时间可构造函数。为了定义一种语言L（C，t），这对于使用上述思想的C来说是困难的，我们首先定义辅助语言Aux（C，t）i，j。这些语言捕获了产生相对于Mi对角化的语言的过程， 第i种语言的机器 根据一些固定的枚举。 我们定义：Aux（C，t）i，−1：={ 0， 1}≤t（i），且对于j≥0，我如果访问M（0i +j，Aux（C，t）i，j−1）具有较少的Aux（C，t）i，j：=元素比rejM（0i+j，Aux（C，t）i，j−1）;从这些集合中定义：L（C，t）i，−1：=n，且对于j≥0，<$L（C，t）i，j−1<${0 +j}，L（C，t）i，j−1，否则。最后，定义L（C，t）为<$i<$jL（C，t）i，j。CC⊆CF∈CF···−···第一章.设F ≠0（t（n））且t（n）2n。< 那么C/F不包含L（C，t）.P屋顶。假设L（C，t）在C/F中。则L（C，t）= L（M i）/f，对Mi中的某台机器和对f中的某台机器.从前面的前提假设，在表示中，接受与M i相同的语言的机器被无限频繁地枚举，我们可以假设i使得t（i）>f（i），因为o（t）。最多有1+2++2t（i）= 2t（i）+11个长度小于或等于t（i）的建议字符串。其中一个长度为f（i）的字符串，比如w，必须是用来表示L（C，t）= L（M i）/f的字符串。 现在考虑字符串0i，0 i+1，0 i+2，. . . ，0 i+ t（i）在L（C，t）中。 由于t（i）<2 i，这些字符串中的每一个都有长度i，所以对于它们中的每一个，M i都会收到相同的建议字符串f（i）。利用w，Mi必须正确回答每个字符串，无论它是否在L（C，t）中。然而，给定L（，t）i，0的定义，长度小于或等于t（i）的所有建议字符串中至少有1/2在0i上回答错误，因此w不能在这些字符串中。在t（i）+1次迭代之后，没有留下可以成功决定每个字符串0 i，0 i+1，0 i+2，. . . ，0 i+t（i）。因此，L（C，t）/=L（M i）/f。Q设w i是长度为t（i）+1的字符串，当且仅当0 i+ j时，它的比特位置j为1L（，t）。 引理1示出了输入0 i，0 i+1，0 i+2，. . . ，0i+t（i）连同长度小于或等于的任何固定通知wJt（i）在至少一个位置上不同于wi。 这样的wi称为硬弦。检查Mi是否接受或拒绝大多数建议字符串的输入是一种概率操作，而不是有界错误概率操作。人们可能试图表明，L（，t）可以通过确定性时间t（n）约简到能够执行上述构造的适当概率类来识别。然而，由于概率运算是强大的，如由PH PPP的事实（23）所证明的，因此将寻求更强的结果。相反，下一个目标是Kannan（15）的建议版本。在输入n、w j和s上定义f M（n，wJ，s），以输出b0b s，其中b j为1（分别为0），这取决于使用建议wJ的长度为n的第j个字符串上的M是否接受（相应地，不合格品）。定义μ M（n，t）为长度为t（n）+1的字典上最小的字符串w，使得对于任何长度小于或等于t（n）的字符串w j，w不等于f M（n，wJ，t（n））。被最小化的长度为t（n）+1的字符串的集合通过在Lemma 1的证明中。设BIT（j，w）为返回w的第j位的函数。 给定w：=µMi（n，t），我们可以通过令0i+j（0≤j≤t（i））为≤≤||..ΣCC| |||||CC当且仅当BIT（j，w）= 1时，一般来说，检查字符串是否具有0 i+j的形式，对于0j t（i），对于次线性时间类来说在计算上是禁止的。然而，我们想要构建包含在次线性时间类中的硬语言要做到这一点，给定x，让j是对应于x的t（i）个 最低有效位的数字。 我们仍然让w：= µMi（n，t），但现在说x在语言中，如果BIT（j，w）= 1，对于从x获得的这个j。这个讨论激发了下一个定义。定义5. 设L µ（C，t）：=L µ（C，t）i，其中L µ（C，t）i定义为：X |X|= i，x = wj，其中|J|为|t（i）| .且BIT（j，µMi（i，t））= 1下一个引理应该是清楚的。2.BABY设F ≠0（t（n））且t（n）2n。< 那么C/F不包含Lµ（C，t）。t（n）2n的条件与引理1中的原因相同。<接下来计算Lµ（C，t）复杂度的上限。请注意，我们对Lµ（，t）的定义隐式地取决于枚举的用途. 对于其余部分，假设该枚举由某个U其通过注释1建立通用性。第三章.设t（n）∈N（logn），t（n）2n.<假设CJ是C的k，并且是可清除的。（3）（。P屋顶。设U（e，x）表示J为. 对于其余部分，假设e= x。这个x可以在O（logx）时间内从x中找到：1、10、100等。在工作带上，并查询辅助输入带上的x，直到找到第一个空白符号。然后删除最后一个0，并将工作带移回左侧。此后，再次向右移动，将0更改为1，并查询输入是否为空。如果它为空，则将1改回0;否则，将其保留为1。当一个已经到达工作磁带的右端再次二进制的长度将被写入。现在考虑co-NTIME（t）（|X|））CJ谓词SOMEDIFF（x，w）：（1）{0，1}=0（|X|））[（n ≤ t（|X|））（<$（U（e，0 |X|+ z，y）惠BIT（z，w）= 1））]。在英语中，对于SOMEDIFF（x，w）成立，必须是这样的情况，对于任何长度小于或等于t的通知y（|X|），则w的第z位不同意C| |C⟨⟩| |⟨⟩||⟨⟩⟨⟩≤||≤|||C |C| |||2| |我在0 |X|+ z，y至少有一个zt（x）. 根据我们的惯例，的二进制数，U（e，0 |X|+ z，y）是U（e，0 |X|+ z，y），因此效果是U计算M e在接收参数0时的计算结果|X|+ z，y。因为e=x，所以e在上面不被视为自由变量谓词SOMEDIFF （x，w）在co-NTIME （t（x）） CJ 中 ，因为猜测y在co-NTIME（t（x））中，并且因为在z上搜索t（x）在DTIME（t（x））CJ中。注意，我们在这里使用J是可清除的，因此UJ（e，x，z，y）：= U（e，0 |X|+ z，y）将是j中的谓词。这对于次线性时间类是需要的，因为人们不会期望能够具有是时候写X 准备输入所需的清除（x，z）位数如果我们用U本身作为神谕。还可以观察到，在次线性情况下，我们使用的是这样一个事实，即我们的机器模型允许元组的编码在一个时间步中分解到辅助磁带上，以便我们可以快速地从输入元组中找出什么是x，什么是wx，wSOMEDIFF（x，w）。最后，我们还应该注意这样一个事实，即对UJ的查询不同的z值是利用我们的机器进入查询状态，并将这些磁带的内容转换为传递给Oracle的元组给定SOMEDIFF（x，w），要计算Lμ（C，t），只需找到一个最小w，使得SOMEDIFF（x，w）成立。2、当x = 0时，x = 0，y = 0。|X|））CJ谓词：（1）{0，1}=0（|X|）+1）[|vy|= t（|X|）+1 SOMEDIFF（x，vy）]。现在让M通过检查EXISTSDIFF（x，0）是否成立来计算Lµ（，t），如果成立，则继续计算额外的位。如果不是，M将0更改为1并计算额外的位。M继续，直到它得到w的所有t（x）+ 1位。最后，M接受当且仅当BIT（z，w）= 1成立。Q将引理2和引理3合在一起给出：第一条。设t∈N（logn），t（n）2n.<假设CJ是C的k，并且是可清除的。假设Fo（t（n））。则C/F /F=3-TIME（t（n））CJ.从时间t（n）到时间t（n）O（1）CJ的过程中，Cai和Watanabe（5）中的证明，即存在一个- 设置需要将使用大小为Nk的电路。我们将再次定义一个谓词，它对枚举中的每个机器e都对角化机器Me与引理3的证明一样，我们将定义一个谓词，其对输入x的计算对于机器Me是困难的，其中e是x的某个增长缓慢但无界的函数。 令（w）i返回t（x）+1位的第i个块，一根弦W. 首先，考虑下面的算法：Lemma3-TIME（t（n）O（1））CJ是引理3 中使用的算法的一部分，以给出一种不是C/F 的语言。SIG3MU（x）：¬| |¬||||||⟨⟩¬||∃ ≤| |1. 假设一个字符串w的长度最多为（t）（|X|）+1）2.2. 对于每个i ≤ t（|X|）+1检查：(a) （w）i的前i位u满足EXISTSDIFF（x，u）。(b) （w）i和（w）i+1的前i位相同。(c) 对于所有长度为t的字符串v（|X|）+1，且初始i − 1位与（w）i相同，如果v的第i位为0且（w）i为1，则<$SOMEDIFF（x，v）。回想一下，在引理3的证明中，EXISTSDIFF（x，u）和SOMEDIFF（x，u）用于对角化机器M e，其中e写在它们的定义公式中，但我们说e=x。 下面我们假设e实际上是x的一个增长更慢的函数。为了简化讨论，如果v和v j的前j位相同，则设PREEQUAL（j，v，vJ）成立。 到将SIG 3MUin设为Σ2-TIME（tO（1））CJ谓词，SIG2MU（x），隐式SOMEDIFF（x，v）中的存在量词需要删除。所以经过猜测w，在SIG2MU中，建议串y也被猜测为长度t（2（n +2 t（n）+t（n）+4））（下面描述该大小的原因），并且假设对于某个固定k，t（2（n+2 t（n）+t（n）+4））小于t（n）k。 假设t是单调的，这个假设意味着t（n）必须在O（n O（1））内，因为如果t（n）增长得比这快，那么对于任何固定的k，t（2（n+2 t（n）+t（n）+4））> t（t（n））将比t（n）k增长得快。 现在可能的是，有了这个建议y，谓词U（e，x，j，u，v，y）成立，当且仅当u扩展到长度为j的字符串v证明SOMEDIFF（x，v）。更正式地说，我们想要一个建议y，使得U（e，x，j，u，v，y）成立，当且仅当以下谓词PREFIXNOT（j，u，x，v）成立：（1）（1）（2）（3）（|u|，u，uJ）（10 - 12）|X|）+1）（U（e，0 |X|+ z，uJ）惠BIT（z，v）=1）]。对于我们的SIG2MU定义，将假设这样的y存在。最终构建的最终语言将是SIG2MU和另一种处理硬度的语言的联合，当这样的y在给定长度不存在同样，使用U（e，x，j，u，v，y）表示U（e，x，j，u，v，y）的约定正如我们上面所说的，在当前设置中，e是x的不同函数，然后在引理3中，并且在证明结束时固定。如果这样的y存在然后SOMEDIFF（x，v）可由DTIME（t（x））CJ-谓词（j）t（x））U（e，x，j，v，y）. 为了正确性，必须在SIG2MU（x）中添加检查，确保U（e，x，j，u，v，y）确实计算PREFIXNOT（j，u，x，v）。一个校验--| |⟨⟩| |∈||C F| |∈{|联系我们 |}||| | | |≤| | ≤⟨⟩||≤||||就是：（1）{0}|X|））（n ∈ {0，1}≤t（|X|）+1）（j ≤ t（|X|））[PREFIXNOT（j，u，x，v）→ U（e，x，j，u，v，y）]。这是在c o-NTIME（[t（n）]O（1））CJ中，并且证明PREFIX NOT（j，u，x，v）蕴涵U（e，x，j，u，v，y）。对于另一个方向，为了确保U（e，x，j，u，v，y）意味着PREFIXNOT（j，u，x，v），检查（1）（n = 0，1）（n=0， 1）（n= 0，1）（n= 0， 1）[U（e，x，j，u，v，y）→（n ≤ t（n）+1）（U（e，0 |X|+ z，u）惠BIT（z，v）= 1）]并且（2）（j≤t（n））（u∈ {0， 1}≤j−1）（v∈ { 0， 1}≤t（n）+1）[U（e，x，j，u，v，y）→U（e，x，j，u-0，v，y）<$U（e，x，j，u-1，v，y）]两者都成立，其中，再次，n=x。我们认为（2）的j = 0的情况是平凡满足的，因为对u的量化是检查u是否在0，1- 1中，我们认为这是空集。（1）和（2）都是co-NTIME（t（n））CJ检查，因此SIG 2 MU（x）是一个12-TIME（[t（n）]O（1））CJ谓词，如果 y存在，则对于 小于或等于t（n）的长度的建议是困难的。 如果y不存在，则PREFIXNOT（j，u，x，v）本身对于e和长度小于或等于t（2（n + 2 t（n）+t（n）+ 4））的建议是困难的。表达式2（n +2t（n）+t（n）+4）限定了对元组j，u，x，v进行编码的字符串的最大长度 （jt（n），n = x，v t（n）+1，u t（n），并且一个在代码中有三个逗号）。也就是说，如果考虑PREFIXNOT（w），其中w编码j，u，x，v，则PREFIXNOT（w）对于长度小于或等于t（w）的建议来说对于e是困难的如果t=（logn）且t（n）2n（对于除n以外的所有情况都是0AC0[m]，其中AC0[m]由那些由多项式大小的电路族决定的语言组成，这些电路族具有与、或、非或MODm类型的无界扇入门。如引言所述，TC0用于表示由恒定深度阈值电路决定的语言。类ModPH是包含P的语言的最小类，使得如果A在ModPH中，那么对于某个m，PA和ModmPA也在ModPH中。 如果存在某种非确定性预言，则语言B处于ModmPAKKK∈/∈/∈∈C ∈ C机器M与OracleA，使得对于所有x，x在B中当且仅当M所在的路径数接受x是m的倍数。Parberry和Schnitger（18）定义了阈值图灵机（TTM）的概念已知类uTC0等于在对数时间内在TTM上确定的语言，并且不断地应用许多阈值运算;而CH正是在多项式时间内由TTM确定的语言，类似地，Allender（1）定义了σ-机的概念，并指出uACC对应于这类机器上的对数时间，ModPH对应于这类机器上的多项式时间在这两种情况下，Allender认为这些机器都享有磁带减少的特性，并且在他的对角化证明中认为，在这两个模型中存在通用机器U，它在大约i3步中模拟机器Mi的一个步骤（在这些模型之一中通过在这样一个通用机器上附加一个线性步数的倒计时时钟，可以得到对于包含uTC0的类，CH是N，类似地，对于包含uACC的类，ModPH是N。注意到3-TIME（nk）CH=CH和3-TIME（nk）ModPH=ModPH，以及回顾定理1，给出下一个推论的证明：推论3。 对于每个k∈N，我们有：(1) u TC0/poly k不含CH。(2) u ACC/poly k不含ModPH。6. 选择集蕴涵现在探讨定理2对选择集的推论。Selman（22）在可计算性理论的半递归集的基础上定义了P-选择集后者的集合以前曾被用来研究半成员算法。P-选 择 集 模 型 是 半 可 行 计 算 的 一 个 方 面 ， 也 得 到 了 广 泛 的 研 究 。Hemaspaandra和Ogi- hara（11）和Hemaspaandra和Torenvliet（12）的书为这些集及其文学提供了很好的介绍。定义6. 一个语言L是自适应的，当且仅当存在一个R（x，y）使得：如果xL，但yL，则R（x，y）成立;并且，如果xL，但yL，则R（x，y）不成立。对于所有不同的字符串x和y，R（x，y）和R（y，x）中必须有一个成立，并且R（x，x）应该总是成立。C/P-sel通常用多项式可计算函数f（x，y）来定义，它输出x或y，这样，如果两个字符串中只有一个在语言中，那么输出那个字符串。再多花点功夫，就可以用函数（10）定义像NP-sel这样的类。这些定义与定义6是等价的，其中是P或NP。定义6对我们来说稍微方便一些，因为它完全是根据语言类而不是函数类来定义的。为了在P的情况下看到这两个定义是等价的，假设对于某个语言L有一个多项式时间的f（x，y）选择器。 可以假设f通过定义fJ（x，y）为f（min（x，y），max（x，y）），在其参数中是对称的这可以被验证为仍然是L的选择器。对于这个fJ，定义R（x，y）为fJ（x，y）=x。注意，如果x在L中，但y不在L中，则R（x，y）成立，但R（y，x）不成立。 类似地，如果x不在L中，但y在L中，则R（x，y）不成立，但R（y，x）成立。确实成立最后，请注意，如果x和y都在语言中或都不在语言中，那么当一个fJ（x，y）=x和fJ（x，y）=y成立时，R（x，y）和R（y，x）之一也成立。我们已经定义了FJ使得FJ（x，y）=FJ（y，x）所以这两种情况中只有一种是可能的。对于另一个方向，假设现在有一个有一个多项式时间R（x，y），如定义6所示，如果R（x，y）成立，可以定义f（x，y）输出x，否则输出y。这可以很容易地被检查为选择器。Ko（16）证明了P-sel包含在P/quadratic中.这一点的一个证明如下：设L通过关系R（x，y）在P-sel回想一