电路计算能力：恒定宽度多项式大小的圆柱形电路与不确定性分支程序的关系

1x2x3x4x2x3x4x5x1x2X3X4X1X2X3X4X5电路上的寄生虫KristofferrArnsfeltHansenpeteterBroMiltersenn摘要我们考虑的计算能力的恒定宽度多项式大小的圆柱形电路和不确定性分支程序。我们表明，每一个功能计算的一个2.2×MOD×AC0电路也可以计算的一个恒定宽度的多项式大小的圆柱形不确定性分支程序（或圆柱形电路）和每一个功能计算的一个恒定宽度的多项式大小的圆柱形电路属于ACC0。1介绍图1：一个宽度为2的圆柱形分支程序计算奇偶校验.本文考虑了等宽度、多项式长度的圆柱分支程序和回路的计算能力众所周知，在宽度受限电路和深度受限电路的计算能力之间存在粗略的相似性，但是这种相似性不是完全等价的。 例如，由具有拟多项式大小和多对数深度的电路族计算的函数类等于由具有拟多项式大小和多对数宽度的电路族计算的函数类。另一方面，由多项式大小和多对数宽度的电路族（非均匀SC）计算的函数类通常被证明不同于由多项式大小和多对数深度的电路族（非均匀NC）计算的函数类。 对于恒定深度和宽度的情况，在计算能力上存在可证明的差异;由多项式大小的恒定深度电路可计算的函数类，即AC0，是由多项式大小的恒定宽度电路（或分支程序）可计算的函数的真子集，后者是，由Barington的 T h e orem [ 1 ] ， t h e bigg e r c l a ss N C 1。 此外，Vinay[7]和Barringonetal[2，3]表明，通过对计算施加几何限制，差异消失了：可由平面，恒定宽度，多项式大小电路（或非确定性分支程序）计算的函数类正好是AC0。因此，AC0和NC1都可以通过恒定宽度以及通过奥胡斯大学计算机科学系BRICS，BasicReearchinComp uterSci ence（www. brics. dk），由DanishNati onalReearchFo nundati on创建。我的朋友：{arnsfelt，bromille}@daimi. 一位联合DK印度科学研究所，班加罗尔，印度。Email：vinay@csa. iisc. ernett。In2i=1xi∈A（modm），否则为0我们让MOD表示家庭恒定深度电路模型然后，很自然地会问，是否可以类似地通过一些自然的恒定宽度电路或分支程序模型来捕获由各种恒定深度电路模型（例如ACC0和TC0）定义的AC0和NC1之间的类在本文中，我们作出了一些进展，回答这个问题，考虑一个稍微宽松的几何限制比平面性：我们考虑的函数计算的圆柱多项式的大小，恒定宽度电路（或不确定性分支程序）。非正式地（正式定义见下一节），一个分层电路（分支程序）是圆柱形的，如果它可以嵌入在圆柱体的表面上，使得每一层都嵌入在圆柱体的一个横截面上（与其他层的横截面不相交），没有导线相交，并且两层之间的所有导线都嵌入在圆柱体的两个相应横截面之间的部分上（见图1）。它是直接的，恒定宽度的多项式大小的圆柱分支程序有更多的计算能力比恒定宽度的多项式大小的平面分支程序：后者只计算功能在AC0[2]，而前者可以计算奇偶性（见图1）。我们问他们的确切计算能力是什么，并表明他们的能力并没有超出计算功能，如奇偶校验。事实上，它们只能计算ACC0中的函数。准确地说，本文的第一个主要结果是下面的下界的权力的圆柱计算。定理1由多项式长度为2 × 2× MOD × AC0的电路计算的每一个布尔函数也可以由一个定宽多项式长度的圆柱形非确定分支程序计算。通过一个2× 2MOD AC0电路，我们指的是一个多项式大小的电路，在输出端有一个与门，一层或门馈送与门，一层MODm门（可能是许多不同的常数界值的m）馈送或门，一个（多输出）AC0电路馈送MOD门。目前还不知道是否列入适当。我们证明定理1的直接建设，推广和扩展图1的简单思想。我们的第二个主要结果是下面的上界的权力圆柱计算。定理2由一个等宽、多项式大小的圆柱形回路计算出的每一个布尔函数，ACC0.定理2的证明是本文中技术性最强的部分。通过使用有限幺半群理论和Barrington和Therien[4]的结果进行模拟（如许多关于恒定宽度计算的先前结果）。因此，我们显示包含有关的计算圆柱电路解决字问题的某一有限幺半群，然后表明，这个幺半群是可解的。一个标准的模拟表明，每个布尔函数计算的恒定宽度，多项式大小的圆柱形非确定性分支程序也计算的恒定宽度，多项式大小的圆柱形电路。为了完整起见，我们在命题3中描述了这个模拟。因此，可以与“cycylindricalcirucut”交换组织文件在第二节中，我们正式定义了圆柱分支程序和回路的概念。我们还概述了我们使用的代数工具在第3节中，我们证明了定理1。在第五节中，我们证明了定理2.由于这个证明是相当技术性的，我们通过在第4节中展示一个稍微简单的证明来热身，即圆柱分支程序（而不是电路）只计算ACC0中的函数。最后，我们在第6节中进行了一些讨论并提出了一些悬而未决的问题。2预赛有界深度电路令A{0，. . .，m-1}。 使用Grolmusz和Tardos的符号[5]，MODAgate takesn布尔乌姆里奇输入x1，. . .，xn，输出1，如果3M关于MODA门的所有常数有界m和所有A。同样地，AND和OR表示无限扇入AND和OR门。如果G是一个布尔门族，C是一个电路族，我们让GC表示由一个G门以C的电路作为输入组成的多项式大小的电路族AC0是由非门和无界扇入与门和或门组成的多项式大小的有界深度电路计算的函数类ACC0是当我们也允许无界扇入MOD门计算常数k的MODk时计算的函数类。我们还将使用AC0和ACC0来表示计算相应类中语言的电路类。圆柱形分支程序和电路一个有向图D =（V，A）称为分层图，如果存在一个划分V = V0<$V1<$··<$Vh，使得A的所有弧都从Vi到Vi+1. 我们来看看D的最后一点，|Vi|最大值为k=max，|Vi|D.Let[k]dentente g ers{1，. . . ，k}。 对于a，b∈[k]，其中a/b+1（mdk），我们在[a，b]中找到（cyclic），使其成为集合{a，. . . ，b}ifa≤bandd{a，. . . ，k}{1，. . . ，b}ifa>b。 如果m∈ b + 1（m o d k），则m∈t（a，b）=[a，b]\{a，b}，m∈t（a，b）=[k]\{a，b}.设D是一个分层有向图，其中所有层的宽度为k。我们将假设每层中的节点编号为1，. . .，k，并通过这些数字来指代节点。如果满足以下性质，则D被称为圆柱形：对于从层l到层l+1的每一对连接节点a到节点c和节点b到节点d的弧，以下必须成立：层l的区间（a，b）中的节点只能连接到层l + 1的区间[c，d]中的节点，并且层l的区间（b，a）中的节点只能连接到层l + 1的区间[d，c]中的节点。注意，这相当于说层1+1的区间（c，d）中的节点只能连接到层1的区间[a，b]中的节点，并且层1+1的区间（d，c）中的节点只能连接到层1的区间[b，a]中的节点。一种新的数据挖掘方法是一种灵活的方法，其中，通过这种方法可以实现所有的数据挖掘，即变量或被求反的变量、或布尔常量、以及初始节点和终止节点。当且仅当图中存在从初始节点到终端节点的路径时，输入被接受，该路径是根据输入将常量替换为文字然后删除标记为0的弧我们将只考虑分层形式的分支程序，也就是说，将其视为分层的有向图。我们可以假设初始节点在第一层，终端节点在最后一层，而且这些是这些层中唯一与弧相关的节点。 我们还可以通过添加虚拟节点来假设所有层具有相同数量的节点圆柱形分支程序是指分层形式的有界宽度的不确定分支程序，当被看作是有向图时，它是圆柱形的圆柱形电路是由扇入2 AND和OR门以及扇入1 COPY门组成的电路，当被视为有向图时，它是圆柱形有向图。输入节点可以是文字或布尔常量。输出门在最后一层。我们可以假设所有层都具有相同数量的节点，通过将虚拟输入节点添加到第一层并将虚拟COPY门添加到其他层。一个标准的模拟不确定性分支程序的电路扩展到圆柱形分支程序和圆柱形电路。我们给出了完整的细节。命题3由一个宽为k，深为d的圆柱分支程序计算的函数，也可由一个宽为O（k），深为O（dlogk）的圆柱回路证明用一个或门替换分支程序中的每个节点。用一个新的与门替换从节点u到节点v的每个弧，用文字x标记，用一个新的与门接收两个输入，门u和文字x，并用与门的输出馈送门v。1我们的定义稍微偏离通常的定义，其中节点而不是边缘由文字标记，并且未标记的节点被 称 为 特 殊 的 非线 性 “ c h o i c e “ - 节 点 ， 但 它 很 容 易 被 看 作 是 一 个 简 单 的 非 线 性 方 程 - 在 这 种 情 况 下 ， 它对 我 们 来 说 更 方 便 。41M这种变换明显地保持了图的圆柱性此外，电路的宽度与分支程序的宽度成线性关系所得到的OR门可以具有大于2的扇入我们用扇入两个或门的树来替换每个这样的门，保持宽度并将深度放大最多O（logk）的因子Q幺半群与群Letxandybel ementsofagroupG. x和y的坐标是元素tx−1y−1xy。由G的所有交换子生成的子群G（1）称为G的交换子子群。一般地，letG（i+1）不表示G（i）的子群的系数。 如果G（n）是对所有n的一个独立的群，则G是独立的。 因此，阿贝尔群，特别是循环群，是可解的。幺半群是一个具有结合二元运算和双边恒等式的集合MM的子集G是M中的群，如果它是关于M的运算的群。注意，M中的群G不一定是M的子幺半群，因为G的单位元不一定等于M的单位元。M称为可解群，如果M中的每个群都是可解群。有限么半群M的字问题是计算乘积x1x2。. . 给定x1，x2，. . .，xn作为输入。Barrington和Therien[4]的一个定理指出，可解有限幺半群的字问题在ACC0中。3用圆柱分支程序模拟有界深度电路在这个领域，我们将审查第一项。作为一个观点，我们已经使用了由Vinay [ 7 ]和B a rn g t o nt a l [ 2 ]确定的“唯一”部分。为了完整起见，我们将其包括在“所有“部分中。定理4一个语言是AC0的当且仅当它能被一个多项式大小的常宽平面分支程序接受。这里平面分支程序是一个分层分支程序，满足，对于从层l到层l+1的每对弧，连接节点a到节点c和节点b到节点d，如果a b<，则c≤d。我们需要一些简单的观察。首先观察到，如果我们可以用平面（圆柱形）分支程序模拟一类电路C，那么我们也可以通过简单地连接适当的分支程序来用平面（圆柱形）分支程序模拟AND_C组合分支程序的另一种方法是通过替换，我们简单地用分支程序替换对应于特定文字的边。这一点的影响在下面的引理中得到了体现。Lemma5Iff（x1，. . . .. . . ，gn和dg1，. . . ，例如，由具有大小为2且具有2个N（g1，. . . ，gn）是由一个具有大小为O（s1w1s2）和宽度为O（w2w2）的并行（cylindrica l）算法生成的。·1··1 ·1·x1x2·1 ·1xn−1xn··1 ·图2：一个平面分支程序计算OR。将上述观察结果与图2中的结构相结合，模拟OR门，我们可以清楚地看到图4中的“唯一”部分。模拟MODA如果不考虑图3中的顶部节点，第一层和最后一层，并修改第二层到最后一层之间的连接，以将集合A带入5M11acc out. 结合Lemma5的连续性、L e m a 4的“唯一性”和多项式扇入AND下的圆柱分支程序的封闭性，我们建立了用有界宽度多项式尺寸的圆柱电路模拟ANDANDMOD_AC_0电路.•X11X1x1•x2x2x2··xn·xnxn1·1 ·x11x1•X2X2•·xnXn·1 ·1··x11x1•X1•X2X2•X2··xn··xn1··xn·图3：MOD4的圆柱形分支程序片段.图3所示的结构实际上有更多的用途，可以将其视为M2，其中M2是[2]上二元关系的幺半群分支程序的一般构造对于MOD A，采用n个输入的片段如下：不失一般性，我们可以假设，|一|= 1个实际上，A={ 0}，因为我们的目标是模拟OR MOD。分支程序片段将具有n+ 3层。第一层和最后一层的宽度为2，中间层的宽度为m。第一层中的顶部节点具有到除节点1之外的所有节点的弧，并且底部节点具有到节点1的弧。最后一层中的顶部节点具有来自除A中的节点之外的所有节点的弧，并且底部节点具有来自该节点的弧。中间层中的节点以显而易见的方式表示输入的前缀模m的和现在考虑图4所示的M2当模拟MOD门评估为0时，刚刚描述的分支程序片段分别对应于m= 2和m >2的（a）和（b）。在这两种情况下，当模拟MOD门评估为0时，片段对应于（c）。···· ·· ······ ·· ··（一）（b）第（1）款（c）第（1）款（d）其他事项图4：M2的一些要素.现在，我们可以描述我们的结构，模拟或MODMOD电路。该构造在MOD门的分支程序片段之间交错（d）的分支程序片段。此示例可以看到，在M O D g的值为1的情况下，一个较短的循环会产生一个缓冲区。最后，我们在两端添加层，为模拟挑选适当的节点。整个结构如图5所示。正确性很容易验证。ORRRMODcircuits的相似性、第4行和第5行的“唯一”部分以及多项式扇入AND下的圆柱分支程序，共同完成定理1的证明··Mod1··Mod1··11··MOD·1 ··1··1 ··1··1 ·图5：一个计算MOD的圆柱分支程序。6Aπ（x）AA˜˜4用有界深度回路模拟圆柱分支程序在这一节中，我们将对下一节中将要给出的定理2的证明进行热身，通过给出一个更简单（但类似）的证明来证明一个较弱的结果，即有界宽度多项式大小的圆柱形非确定性分支程序只计算ACC0中的函数。实际上，我们已经在ACC 0中对下面的“分支程序”进行了定义：给定一个宽度为k的圆柱形分支程序及其变量的真值赋值，决定程序是否接受。由于通过宽度为k的圆柱多项式大小分支程序计算的任何函数显然是BPV k的Skyum-Valiant投影[6]，因此我们将完成。我们将证明，BPVk是在ACC0表明，它减少，由AC0减少，字的问题，我们定义的幺半群Mk下。然后，我们证明了么半群Mk是可解的，并且由于这意味着，根据Barrington和Therien[4]的结果，Mk的字问题是在ACC0中，我们的证明将是完整的。我们将Mk定义为[k]上的二元关系的幺半群，其捕获嵌入在圆柱上的宽度k分支程序的计算，在以下意义上：Mk是由表示弧如何在宽度k圆柱有向图中的两个相邻层之间行进的所有关系生成的幺半群。 幺半群运算是二元关系的常用复合运算，即，若A，B∈Mk且x，y∈[k]，则xABy惠<$z：xAz<$zBy.BPVk通过以下AC0归约将Mk的字问题归约为：根据真值赋值将分支程序中现在考虑圆柱有向图D，它只由与常数1相关联的弧然后，分支程序接受给定的输入，当且仅当存在从D的第一层中的初始节点到最后一层中的终端节点的路径。 我们可以通过简单地将D分解为序列A1，A2，. . . ，Ah，计算乘积A = A1A2···Ah，并检查这是否不同于Mk的零元素。因此，我们只需要证明Mk是可解的。我们的证明由下面的更强有力的陈述来完成。命题6 M k中的所有群都是循环群。证明设G∈Mk是具有单位元E的群.设A∈G，R是所有x的集合，使得xEx。正如下面将要展示的，考虑R的元素就足以捕捉A的结构。设x∈R.由于AA−1=E，存在z使得xAz和zA−1x。由于A−1A=E，它遵循zEz，即z∈R。因此，存在函数πA：R→R，使得x：xAπ（x）<$−1x为了使A可由π A简单地表示，我们在A ∈[k]中找到一个新的矩阵，使得xA∈πA（x）=y。这就是说，Ais只是πAvie wdasare lation。 如果AAAA EE=A。 Converse lyletxAy. 由于EkA= A，存在z ∈ R使得xEz和zAy。由于πA（z）A−1z，我们得到πA（z）Ey。 即xEz，zA<$πA（z）andndπA（z）Ey。 你是我的朋友。因为我们有一个A=EAE。我们希望有一个基础，即πA是一个pmutatin，而πA{|A∈G}是一个group。这是一个很好的例子不为真，因为E可以是Mk中的任何传递关系。为了实现这一点，我们将首先使用以下关于[k]的等价关系来简化G的元素的结构，xEy惠（xEy惠yEx）x = y。LetA∈G. Ifxx′andyy′thenxAy惠x′Ay′，其中EAE=A。 Agiverio nAgin[k]/n，其中rexAy惠[k]xAg i[k]y和di将满足hat{Ag i n|A∈G}是G的一个同构群.因为我们知道AB=AB。ABBy：[k]xA我们可以在Mk中找到这个群的同构副本如下。 选择每个等价类[k]x在[k]x中的代表r（[k]x）。在[k]上定义一个关系C，使得xCy惠x=y=r（[k]x）。因此7Aπ（x）AA[k] x：r（[k]x）Cr（[k]x）。设σ：G→Mk由σ（A）=CAC给出.则σ（G）是G的理想同构副本。因此，我们可以假设关于n的等价类的大小为1。现在我们回到πA的研究上来。下面的性质，即对于x，y∈R，xEy惠成立，πA（x）EπA（y）满足：IfxEytenπA（x）A−1ysinceA−1E=A−1。 AsA−1A=EitfollwsthatπA（x）EπA（y）.如果π A（x）EπA（y），则xAπA（y）是xAπA（x）且AE=A的连续性。AsπA（y）A−1yanddAA−1=E然后，它遵循xEy。我们现在可以得出结论：πA是R上的置换：如果πA（x）= πA（y），那么πA（x）<$πA（y），所以x <$y，thatis，x=y。AlsoπAisuniquelydedefinedd：AssumeπA：R→Rsatisfiesx：xAπ<$（x）<$−1xLetx∈R。 我们在πA（x）中没有任何一个是π A（x）<$πA（x），所以πA（x）=πA（x）。HenceπA=πA。NWecnc onc ludethat{πA|A∈G}是一个与G同构的随机过程. 为此，我们需要证明πAB= πB<$πA。设x∈R. 因为xAπA（x）和πA（x）BπB<$πA（x），所以xABπB<$πA（x）成立。−1由于πB<$πA（x）B−1πA（x）和πA（x）A−1x，因此遵循πB<$πA（x）B−1A−1x，即πB<$πA（x）（AB）x因为πAB是唯一定义的，所以结果如下。To show w that{πA|A∈G}是一个周期性的函数，它可以很容易地从圆柱性的定义中得到事 实 ： A 是 一 个 可 以 直 接 根 据 需 要 进 行 设 计 的 系 统 。Letp1 0是极小的.然后，如引理7所示，简化所得到的电路。这是一个简单的看到这一点是一个homom 我们将其归类为连续数据流实际上是一个Nk电路。为了证明这一点，我们必须论证上述构造并没有引入新的常数输出nodes。这一例子可以看出：LetCanddC′beNigkcircuitscommputinggfanddf−1∈G. 如果在C的构造中引入新的常数输出节点，则该节点已经是电路C <$C′中的常数输出节点，计算e，因为C′在C <$C′中向C馈送与在上述构造中馈送给C的常数相同的常数。然而，这与上述说法相矛盾。因此φ是从G到Nk的同态。我们现在只需要证明它是内射的，我们是DONE。 LetCandCebeNkcircuitscmp utingf∈Gande，其中fff=e. 我们有一个关于x的等式，C（x）/= Ce（x）。由于S中的输出节点具有相同的值，因此存在不在S中的输出节点，其中值不同。通过注意上述构造保留了不在S中的输出节点的值，我们得到φ（f）（x）/=φ（e）（x）。Q现在我们可以转向幺半群Nk的研究。注意，它是由深度为1Nk的电路产生的。这在我们将证明的以下一些性质中将是有用的，因为它允许我们通过归纳来考虑深度为1的电路。9与[3]中一样，用{0， 1}k中的最大1-区间的集合来标识输入向量将是方便的，仅在这里我们考虑循环区间。例如，向量1010011011是用区间{[3， 3]，[6， 7]，[9， 1]}。我们只对至少包含一个区间的输入进行这种识别，也就是说，我们忽略向量0k和1k。引理9设x ∈ {0，1}k包含m个区间，f ∈ Nk. 则f（x）至多包含m个区间。 如果f（x）实际上包含m个区间且m ≥ 1则f（x）={f（I）|I ∈ x}。证明清楚f（0 k）= 0 k和f（1 k）= 1 k，所以我们可以假设m ≥ 1。 假设C是计算f的深度为1Nk的电路。 设c，d ∈ [k]是在输入x上求值为1的节点。c和d中的每一个都必须有一个从x的区间开始的弧。假设c和d有来自x中相同区间I的弧，比如从a到c，从b到d。 [a，b] I或[b，a]I。 如果[a，b] I，则区间（c，d）中的所有节点的值都为1，因为它们必须从[a，b] I取弧。 类似地，如果[b，a] ≠ I，则区间（d，c）中的所有节点的值都为1。因此，在x中具有相同间隔的弧的节点在C（x）的相同间隔中（如果有的话），并且第一部分如下。现在假设C（x）中也有m个区间。为了展示第二部分，我们必须排除C（x）中的一个区间可以从x中的多个区间获取弧。但如果是这种情况，也会有不同的间隔与弧从相同的间隔在x，矛盾的上述。Q任何{0， 1}k的子集通过逐点提升阶0 1而成为偏序集。

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