小复杂性类的相对化理论

小复杂性类的相对化及其理论Klaus Aehlig<$Stephen Cook阮晋勇§ 2012年4月26日摘要Ex是NC1，L-的相关线性代数的定义，而NL不在NC1L-，NLAC1 中提供该信息。我们是通过给他打电话第一个定义是，它使我们能够重新审视它。HereforL-我们将他们的定义，使用Wilson的堆栈Oracle模型进行相对化我们证明了两个W的坍缩是在{AC0（m），TC0，N C 1，L-，NL }中实现的，并且证明了两个W的坍缩是在{AC 0（m），TC 0，N C 1，L -，N L}中实现的他们的相对化。接下来，我们展示一个使ACk（α）一个合适的等级制度这加强和澄清了[Takeuti，1995]中相对化理论的分离。其思想是，一个电路的嵌套深度的预言门是有限的，由k不能正确计算的（k+ 1）组成的每一个预言功能。最后，我们通过修改后两位作者先前定义的理论，发展了描述P的子类的相对化的理论。一个函数在一个理论中是可证明的全的，只要它在相应的相对化类中，因此神谕分离意味着相对化理论的分离1介绍把P从NP中分离出来的预言和把NP压缩成P的预言都已经被构造出来了。这就排除了用相对化方法证明P和NP分离或崩溃的可能性然而，类似的结果不需要为P类和N类的子类列出。Indeed，priortoo这项工作还没有一个令人满意的定义的相对化版本的同时保留内含物的NLNC1L-NLAC1（1）（本文中NCk和ACk指的是它们的统一形式。） 例如[LL76]，如果允许图灵机在以下情况下是不确定的，这篇论文的初步版本是[ACN 07]。†由DFG赠款Ae 102/1-1支持由NSERC支持§由NSERCarXiv：1204.5508v1 [cs.CC] 2012年4月2写oracle查询，则有一个oracle α，使得NL（α）/NLP（α）。后来NL（α）的定义采用了[RST 84]中规定的要求，即只要oracle磁带（或oracle堆栈）非空，非确定性oracle机器就是确定性的。则包含NL（α）<$P（α）相对化，但不是（1）中的所有包含相对化。由于在一个预言机NC1电路中预言机门的嵌套深度可以大于1，NC1L-必须允许一台oracle logspace图灵机访问更多多个Oracle查询磁带[Orp83、Bus86、Wil88]。 对于定义为Wilson [Wil88]，部分构造的oracle查询存储在堆栈中。机器只能在堆栈顶部的oracle磁带上写入查询它可以在一个空的oracle磁带上开始一个新的查询（从而下推当前的oracle磁带，如果有的话），或者查询顶部磁带的内容，然后它变成空的，栈被弹出。继Cook [Coo85]之后，相对化NC1中接受语言的电路是那些具有对数深度的逻辑门，其中布尔门具有有限扇并且m个输入的Oracle门将log（m）贡献给其父门的深度。在NC1NL-中，由Wilson [Wil 88]定义的逻辑块需要满足以下条件：在任何时候，克i=1max{log（|QI|），1}= O（log（n））其中q1，q2，. . . ，q，k是堆栈的内容，|QI|是他们的长度。对于用这样一个Oracle对数空间机模拟一个OracleNC1电路，其上界O（log（n））是不能改进的.由于L-（α）和NL（α）的定义都是由NC1（α）<$L-（α）构成的，因此，我们不完全知道NL（α）<$AC2（α）[Wil88];NL（α）<$AC1（α）的定义是开放的。我们观察到，如果oracle堆栈的高度由一个常数限制，（而查询的长度仍然由输入长度的多项式来限制），则可以通过oracle AC1电路来模拟oracle NL机器，即， NL（α）=1（α）。事实上，可以证明NL（α）包含在有向图可达性问题的AC 0（α）闭包中，而L-（α）方程则包含出度至多为1的有向图可达性问题的AC 0（α）闭包.布尔语句值问题的AC0（α）闭包（对于NC1是AC0完全的）被证明是可由统一的oracleNC1电路（如前所述定义）计算的语言，其中oracle门的嵌套深度现在由一个常数限制。我们使用这个对预言门的新限制重新定义了NC 1（α）;新的定义更适合于AC0（α）约简的上下文中（当考虑NC1（α）约简时，NC 1（α）的先前定义似乎是合适的）。从而得到了NC1（α），L-（α）和NL（α）的第一个定义，并对（1）中的结论进行了改进.进一步地，对于相应的相对化，对于NC1，L-，和NL的AC0-完备性（也称为AC0（m），TC0）成为AC0（α）-完备性3班因此，任何将上述两个类分开的神谕的存在，都意味着相应的非相对化类的分离（如果非相对化类相等，那么它们的完整问题在AC0-约化下是等价的，因此在AC0（α）-约化下甚至更等价，因此相对化类也会重合分离的关系-相对化的类和非相对化的类一样难以区分这很好地推广了已知的结果[Wil88，Sim77，Wil87]。另一方面，将类ACk（对于k = 0，1，2，. . . ）和P已构建[Wil87]。在这里，我们证明了一个尖锐的相对化电路类之间的分离，其嵌套深度的甲骨文门不同。更精确地说，我们证明了预言门嵌套深度为k的一致电路族不能正确地计算（k+ 1）个迭代复合f（f（. . . f（0）。. . （2）对于所有Oracle函数f。（显然，（2）可以通过具有嵌套深度（k+1）的oracle门因此，有一个预言α，NL（α）<$AC 1（α）<$AC 2（α）<$. . . （3）化学计量学利用（2）来分离相对化电路类的思想已经在Takeuti [Tak95]的工作中出现，在那里它被用来分离一阶理论T LS（α）和T AC1（α）的相对化版本。 这里的T LS和T AC是（singlesorttedd）theorieisassociatdwiththL-AC1分别。 因此与简化的论点，我们加强了他的结果。最后，在后两位作者[CN 10，NC 05]工作的基础上，我们发展了与新定义的分类NC1（α），L-（α），NL（α）相关联的相对化的两类理论，并将其应用于这些相对化的分类。本文的结构如下。在第二节中，我们定义了相对化的类，并证明上述包含。在第3节中展示了一个在（3）中分离类的oracle。在第4节中，我们定义了相关的理论，并使用第3节中定义的预言来说明它们的分离。2相对化小类2.1相对化电路类在本文中，α表示二元串上的一元关系。一个问题是在ACk中，如果它可以通过一个多项式大小的布尔电路族来解决，该布尔电路族的深度由O（（logn）k）（n是输入位数）限制，其中允许无限扇入。相对化的类ACk（α）通过允许除了（无界扇入）布尔门（<$，，）之外，当且仅当门的输入（被视为二进制串）属于α时输出1的预言门（这些门也称为α门）来推广这一点。在本文中，我们总是要求电路族是一致的。我们对均匀性的默认定义是DLOGTIME，这是一个稳健的均匀性概念，4定义的等价数量[BIS 90，Imm99]。特别是，语言L{0，1}{0，1}{0} . .，n}的一些固定的一阶公式，具有未解释的一元谓词符号和被解释为加法和乘法的三元谓词。这里，AC0归约指的是因此，如果存在计算A的均匀多项式大小常数深度电路族，则问题A可AC0约化为问题B，其中允许电路具有B的oracle门，以及布尔门。回想一下TC0（分别为AC0（m））的定义方式与AC0相同，不同之处在于电路允许无界扇入阈值（分别为modm）门。定义1（ACk（α），AC0（m，α），TC0（α））。当k ≥ 0时，类ACk（α）（resp. AC0（m，α），TC0（α））被定义为均匀ACk（分别AC0（m），TC0），除了允许无界扇入α门。类NCk是ACk的子类，通过限制双稳态和双稳态门具有扇入2来定义。定义NCk（α）更为复杂。在[Coo85]中，具有m个输入的oracle门的深度被定义为log（m）。一个电路是一个NCk（α）-电路，只要它有多项式大小，并且从输出门到输入门的任何路径上所有门的总深度是O（（logn）k）。注意，如果有一个大的和小的oracle门的混合，oracle门的嵌套深度可能不是O（（logn）k−1）。这里我们进一步限制了这个定义，要求oracle门的嵌套深度是O（（logn）k−1）。这一限制使我们能够证明，在reelaitizedworld中，NC1仍然是L-中的一个，并且如预期的那样，对于NCk，该电路的最优解（对于oracleNCk电路）仍然是完全定义2（NCk（α））。 当k ≥ 1时，一种语言是在NCk（α）中，如果它可由一个一致的NCk（α）回路族计算，即， ACk（α）电路，其中，因此，时间复杂度是O（（log n）k−1）。下列包含扩展了非相对化类的包含AC0（α）<$AC0（m，α）<$TC0（α）<$NC1（α）<$AC1（α）<$. . . α P进一步地，AC0（m），TC0和NC1的AC0-完全问题对于相应的相对化类也是AC0（α）-完全的这由下一个结果表示，使用以下完全问题：MODm和THRESH（阈值函数）分别对于AC0（m）和TC0是AC0-完全的，而FORMVAL（布尔公式值问题）对于NC1既是AC0-完全的，也是AC0-多-一完全的。3号提案AC0（m，α）=AC0（MODm，α）（四）TC0（α）=AC0（THRESH，α）（五）NC1（α）=AC0（公式，α）（六）5证据右边的每个类都包含在左边相应的类中，因为对完整问题的查询可以由计算查询的电路代替左边的每个类都是右边相应类的子集，因为对左边α的查询具有有限的嵌套深度。Q请注意，AC1（α）或P（α）没有类似的特征，因为这里对α的查询可以具有无限的嵌套深度。2.2相对化的Logspace类为了定义Oracle日志空间类，我们使用Wilson堆栈模型的修改一个优点是这里定义的相对化类在AC0-约简下是封闭的。对于非堆栈模型，这是不正确的具有一堆oracle磁带的图灵机M可以将0或1写入到如果它已经包含一些符号，或者它可以开始在空的甲骨文磁带。在后一种情况下，新的oracle磁带将位于堆栈的顶部，我们说M执行推操作。机器也可以弹出堆栈，它的下一个动作和状态取决于α（Q），其中Q是顶级Oracle磁带的内容。 请注意，这里的oracle磁带是只写的。我们修改了Wilson的模型，只允许一个恒定高度的堆栈（因此在cs L（α）和cs NL（α）中使用前缀“cs”），而不是允许任意数量的Oracle磁带。这使得相对化的类与非相对化的类的顺序相同。在csNL（α）的定义中，我们还使用了限制[RST 84]，即当oracle堆栈非空或处于push状态时，机器是确定性的。定义4（cs L（α），csNL（α））。对于字符串上的一元关系α，csL（α）是可由对数空间计算的语言类，多时间图灵机使用高度由常数限制的α -oracle堆栈。csNL（α）被定义为csL（α），但是当oracle栈为空时，图灵机被允许是不确定的。定理5. NC 1（α）→cs L（α）→cs NL（α）→AC 1（α）。证据 第二个包含是直接从定义，第一个可以是在该测试中进行了验证，并对该产品进行了验证，该产品符合NC1标准-（参见[Wil88]）。最后一个包含实际上可以被加强，如下一个定理所示。Q下一个定理部分地将命题3扩展到两个新类。回想一下，STCONN是一个问题：给定（G，s，t），其中s，t是有向图G的两个指定顶点，决定是否存在从s到t的路径。我们定义1-STCONN是相同的，除了我们要求G中的每个节点的度最多为1。则STCONN和1-STCONN对于NL和L -是AC0-多-一完全独立的。6Kcs L（α）函数的定义是允许csL（α）机器在只写输出磁带上写入。然后，像通常一样定义了多一个csL（α）约简的概念。定理6.（i）csL（α）= AC0（1-STCONN，α）(ii) csNL（α）ε AC0（STCONN，α）(iii) 一个语言在cs NL（α）i中是多-一个cs L（α）-可约为STCONN的。证据首先证明了包含AC0（1-STCONN，α）∈ L（α）在（i）中.在AC0（1-STCONN，α）中，通过对1 - STCONN和α的预言查询，给出了一个由一致多项式长度的常深回路族{Cn}n∈N构成的问题.一个csL（α）机M在输入x上执行深度优先搜索。深度为k的每个αoracle门都使用堆栈高度为k的oracle查询来回答，而对1-STCONN的每个oracle查询都通过对数空间计算来回答。请注意，这个参数对于（ii）中相应的包含不起作用，因为一旦oracle堆栈非空，csNL（α）机器就变成了设计和跟踪网络是一个简单的问题，可以用于STCONN（一个简单的L-I= NL）。现在我们证明包含（ii）。（方程中相应的包含(i)也有类似的证明）。设M是一个不确定的日志空间图灵机，具有一个恒定高度的Oracle磁带堆栈。假设h是Oracle堆栈高度的边界。存在一个多项式p（n），使得对于每个输入长度n和oracleα，M最多有p（n）个可能的配置：u0= START，u1= ACCEPT，u2，. . . ，up（n）−1（7）这里，配置ui编码关于内部状态、工作带的内容和头位置以及输入带头的位置的信息，但没有关于oracle堆栈的显式信息（尽管内部状态可能编码隐式信息）。给定一个长度为n的输入x，我们构造一个有向图序列G0，···，Gh，使得Gk中的节点集Vk由所有对（k，u）组成，其中u是一个配置，k是当前Oracle堆栈的高度（所以0≤k≤ h）。Thus（k，u）表示“h e i g h t k c o n fig u r a t i o n”。不要让我把你的名字输入x上的M可以用kVk中的节点序列来描述。我们想定义边集Ek，（（k，u），（k，u′））∈ Eki（k，u′）可以是（k，u）之后的下一个高度k配置（八）Gk中的边Ek组成并Ek=E0E1K K定义E0由所有对（（k，u），（k，u′））组成，使得u不会导致push或pop，并且u′是u的可能后继者。如果k≥1，那么我们还要求u是确定性的配置。7KKk+1如果k=h，则定义E1为空，如果0≤k h<，则E1由所有K K对（（k，u），（k，u′）），使得u是导致推的确定性配置有一个序列（k +1，v0），. . . ，（k +1，vt）（9）配置使得v0是u的后继，且（（k+1，vi），（k+1，vi+1））∈Ek+1，0≤it，且vt引起pop，u′是vt的后继（假定（k，u）是（k+ 1，vt）之前的最近的k级节点<注意，在从（k，u）到（k，u′）的计算中，序列（9）是高度为k+ 1的节点的序列，并且该序列确定了写在高度为k+ 1的oracle磁带上的字符串Q，因此确定了u′是否是vt的后继。通过对k = h，h − 1，.的归纳，很容易证明（8）。. .，0. 对于k= 0，这意味着M接受xi，并且G0中存在从（0，START）到（0，ACCEPT）的路径。因此，它表明，一些AC0（STCONN，α）电路计算每个图Gk给定的输入x的邻接矩阵。事实上，很容易看到，一些AC0电路与输入x输出的邻接矩阵为每个边缘集E0。因此，它表明，一些AC0（STCONN，α）电路计算邻接矩阵的E1给定输入x和邻接E1矩阵，0≤k h<.这是可以做到的，因为利用对STCONN的oracle查询可以从Ek+1得到序列（9），利用AC0电路可以从这个序列中提取写在高度为k+ 1的oracle磁带上的字符串Q，因此α（Q）可以用来确定u′是vt的后继.请注意，Oracle对α的调用的嵌套深度是h。为了证明（iii），我们注意到方向（α）很容易：输入x上的csNL（α）机器M通过模拟回答输入f（x，α）查询的NL机器M′来回答单个查询f（x，α）到STCONN，并且每次M′需要另一个输入位时，M确定性地计算该位。为了证明（iii）在方向（α）上，我们注意到在证明（ii）中定义的边关系E0可以由cs L（α）机计算。然后如上所述，M接受它的输入xi，如果G 0中存在从（0，START）到（0，ACCEPT）的路径，这是STCONN的实例。Q推论7. 分离任意两个类的预言α的存在性AC0（m，α）<$TC0（α）<$NC1（α）<$csL（α）<$csNL（α）意味着各个非相对化类的分离。证据这是由命题3和定理6（i）和（ii）得出的。 如果任何两个非相对化类相等，那么相应的完全问题将是AC0等价的，因此相对化类将是平等QCor llary8（Rel ativizedImmerman-Szelepcss′enyiTherem）。 csNL（α）在互补条件下封闭。8证据由定理6（iii）可知，任何一个cos-NL（α）中的语言都是cos-L（α）可归约为STCONN的多一语言，它也是AC0可归约为STCONN的多一语言.所以co-cs NL（α）等于cs NL（α）。Q设csL2（α）表示在O（log2）空间和定高Oracle栈中可由确定性Oracle图灵机计算的语言类。推论9（相对化的Savitch定理）。csNL（α）=csL2（α）。证据由定理6（iii）和一个csL（α）函数和一个（ log2）空间函数（对于STCONN）的合成是一个csL2（α）函数这一事实得出推论.Q很容易看出，与类AC0（1-STCONN，α）或AC0（STCONN，α）相关联的函数类在复合下是封闭的，因此我们有以下结果。推论10。 与cs L（α）相关的函数类在复合下是闭的.然而，与cs NL（α）相关联的函数类在复合下是否必然是封闭的，这是一个悬而未决的问题，因为同样的原因，我们不能必然得出结论，定理6的部分（ii）中的包含可以变为相等。一旦csNL（α）机器中的oracle栈变成非空的，它就变成了确定性的，所以不清楚这台机器是否能解决STCONN问题。3分离ACk层次结构考虑相对化复杂性类的一个明显好处是，分离就在眼前。即使AC1在多项式层次中的非相对化包含被强烈地证明是严格的，目前还没有证据证明。知道的另一方面Wilson [Wil 87]证明了预言α W的存在，它使得相对化的ACk-谱系是严格的。在这里，我们重建了Takeuti [Tak95]用于分离弱有界算法中的理论的技术，并用它给出了分离ACk层次的预言α的在下一节中，我们将展示如何使用这个结果与见证定理一起获得捕获ACk层次的相对化理论的无条件分离其思想是，计算第k个k（0）= f（f（. . . f（0）的函数-步骤F本质上是顺序过程，而浅电路表示并行计算。因此，在连续任务中表现良好的电路必须很深。为了避免通过预先计算所有可能的值来规避问题的序列特征，f的定义域被选择得足够大;我们将考虑函数f：{0， 1}n→ { 0， 1}n。当然，对于这样一个大的域，我们不能简单地用一个值表来表示这样的函数这9将字符串上的谓词作为输入，而不需要为每个字符串提供输入位。事实上，一个oracle门潜在可访问的位数是其输入线数的指数因此，我们通过字符串Xi是否属于预言机的语言来表示f（x）的第i这里i是自然数i的一些规范编码，使用logn1位。我们的论点可归纳如下。我们假设一个深度为d的电路(i.e.、电路具有d个级别），假定计算然后我们逐步构造一个预言机，如果d>d，它就欺骗这个电路。为了做到这一点，对于电路的每一层，我们决定如何回答神谕问题，我们这样做的方式与前面的层一致，并且使得第i层的所有电路知道的f最多是fi（0）的值。为了使这种逐步构造成为可能，我们必须在构造过程中考虑部分函数如果A和B是集合，我们用f：A <$B表示f是从A到B的部分函数。换句话说，f是一个函数，它的定义域dom（f）是A的子集，它的值域rng（f）是B的子集。定义11.一个部分函数f：{0，1}n<${0，1}n称为n-序列的，如果对某个k ≤n，0，f（0），f2（0），. . . ，f k（0）都有定义，但fk（0）/∈dom（f）.注意，在定义11中，必须是0，f（0），f2（0），. . . ，f k（0）是不同的。引理12. 设n ∈N，f：{0，1}n<${0，1}n是n-序列偏函数.设M ∈ {0，1}n使得|dom（f）|<2 n.则存在一个（n + 1）-序列扩张f ′ <$f，其中dom（f ′）= dom（f）<$M.证据设a ∈ {0， 1}n\（M ∈dom（f））.这样的a存在于我们对Mdom（f）的基数的假设中。设f′是f的扩张，对所有x ∈ M \dom（f）设f′（x）=a.这个f是所希望的。实际上，假设0，f ′（0），. . . ，f ′n+1（0），f ′n+2（0）都有定义。然后，由于a/∈ dom（f ′），所有的0，f ′（0），. . .，f ′n+1（0）必须不同于a. 因此，这些值已经在f中定义了。但这与假设f是连续的。Q定义13. 对任意自然数n和任意部分函数f：{0，1}n n∈{0， 1}n我们将它的位图βn，f关联为部分函数βn，f：{0， 1}n+logn<${0， 1}以显而易见的方式。更精确地说，βn，f（xv）是f（x）的第i定义，否则定义，其中v是长度为log n的字符串，编码自然数i。如果f：{0， 1}n→ { 0， 1}n是一个全函数，我们定义预言机αf为：αf（w）参与βn，f（w）= 1。1我们用log n来表示log2（n +1）。10因此，αf（w）只能对长度为n+ logn的字符串w成立。紧接着定义13，我们注意到f可以从αf唯一重构。如果α是一个预言，我们定义α[n]为：α[n]（w）参与（α（w））|W|= n + log n），所以α[n]有有限的支持。在下文中，电路指的是2.1节中讨论的oracle电路。我们主要对没有布尔输入的电路感兴趣，因此输出仅取决于预言机。定理14. 设C是深度为d且长度严格小于2 n的任意回路.如果C（α）正确地计算了f的最后一位f∈（0），对于（唯一确定的）f：{0，1}n→ {0，1}n使得αf= α[n]，并且这对所有预言机α都成立，则∈≤ d。证据假设这样的电路对所有预言机都正确地计算f我们必须找到一个见证d≤ d的神谕。首先，在所有长度不同于n+ logn的字符串上任意固定oracle。因此，我们可以假设电路只使用具有n+ logn输入的oracle门。通过对k≥0的归纳，我们定义了部分函数fk：{0，1}n<${ 0，1}n，具有以下性质。（这里我们将电路的电平编号为0，1，. . . ，d− 1.）• f0 f1 f2。. .• 大小|dom（fk）|f k的域的最大值是严格小于k的层中的oracle门的数量。• β n，fk决定了所有严格小于k的级别上的预言门的值。• f k是k序贯的。我们可以取f0为完全未定义的函数，因为f 0（0）= 0，所以f0是0-序贯的。对于归纳步骤，设M是长度为n的所有x的集合，使得对于某个i

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