深度为3的算术电路的同一性测试问题的研究

···计算复杂性电子讨论会，报告编号。150（2005）深度为3电路Neeraj Kayal and NitinSaxena IIT坎普尔，印度{kayaln，nitinsa}@ cse.iitk.ac.in二○ ○五年十二月五日摘要研究了深度为3的算术电路的同一性测试问题.本文首次给出了具有有界顶扇入的双端电路的确定性多项式时间恒等式检验我们还表明，一个最小的和简单的无源电路的秩有界的顶部fanin，计算为零，可以无界。这些结果回答了Klivans-Spielman [KS 01]和Dvir-Shpilka[DS 05]提出的开放性问题1介绍多项式恒等式检验（PolynomialIdentityTesting，PIT）是如下问题：给定运算电路C计算域F上的多项式p（x1，x2，…，xn），判定该多项式是否为同零。除了本身是一个有趣的问题，许多其他著名的问题，如素性测试和二分匹配也减少到PIT。 此外，复杂性理论中的基本结构结果，如IP=PSPACE和PCP定理，都涉及到恒等式测试的使用。第一个用于身份测试的随机化算法是由Schwartz[Sch80]和Zippel [Zip79]独立发现的，它涉及在随机点评估多项式，并接受当且仅当多项式在该点评估为零随后是使用较少随机位的随机算法[CK97，LV98，AB03]和素数测试中涉及的多项式的去随机化[AKS04]，但完全去随机化仍然遥远。最近，Impaggliazzo和Kabanets [IK03]的一个令人惊讶的发展表明，用于身份测试的有效确定性算法也意味着强大的算术电路下限。更具体地说，他们表明，如果身份测试有一个有效的确定性多项式时间算法，那么NEXP没有多项式大小的算术电路。这一结果进一步推动了对这一问题的研究，并随后发展了一些算术电路的限制模型的算法。Raz和Shpilka [RS04]给出了非交换公式的确定性多项式时间算法。Klivans和Spielman[KS01]指出，即使对于深度为3的电路，其中最顶部门的扇入是有界的，确定性身份测试也是一个开放的问题。随后，Dvir和Shpilka [DS05]给出了深度为3的算术电路（最上面的门的扇入有界）的确定性准多项式时间算法（注意，如果最上面的门是一个门，则多项式为零，当且仅当其中一个因子为零，然后问题很容易解决）。本文解决了这一问题，并给出了一个确定性的多项式时间算法，用于这类电路的身份测试我们的主要定理是：1ISSN 1433-80922CCCCΣYCCCCCCC2定理1.1. 存在一种确定性算法，在输入域F上深度为3且次数为d的电路C时，确定电路计算的多项式在时间上是否为零poly（n，d k），其中k是最上面的加法门的扇入，n是输入的数量。特别地，如果k是有界的，那么我们得到了深度为3的电路的身份测试的确定性多项式时间算法。Dvir和Shpilka [DS05]给出了具有计算为零的有界顶扇入的双曲余弦电路的结构结果设rank（）为中出现的线性函数的秩。然后他们证明了这样的简单和最小可以有秩至多polylog（d）。他们还问是否可以将秩的上界提高到O（k）。我们通过给出k= 3的秩为O（log（d））的恒等式来否定地回答这个问题第二节给出了有界顶扇域的双端电路的概述，第三节描述了有界顶扇域的双端电路的恒等式检验2算术电路一般算术电路的下界证明是复杂性理论的核心问题之一。由于问题的难度，研究主要集中在单调电路和有界深度电路等受限模型上。对于单调算术电路，已经示出了大小的指数下界[SS 77，JS80]和深度的线性下界[SS 80，TT 94]然而，只有弱下界已知有界深度算术电路[Pud94，RS01]。因此，考虑了一个更受限制的模型-深度为3的算术电路模型（如果我们假设加法门和乘法门交替使用，则也称为算术电路）。一个多项式电路计算一个多项式的形式：k diC（x）=Lij（x）（1）i=1j =1其中Lij指数下界的大小上的算术运算电路已被证明在有限域[GK98]。对于无限域上的一般双曲双曲回路，只有[SW 99]的二次下界是已知的。目前还没有一种有效的算法来测试多路复用电路的同一性在这里，我们有兴趣研究的身份测试问题的限制情况下的双稳态电路这种情况是由Klivans和Spielman [KS01]提出的挑战，Dvir和Shpilka [DS05]给出了一个准多项式时间2.1先前方法让是一个计算零多项式的非线性电路，如等式（1）所示。 我们称如果没有和为零的乘法门的真子集，则为极小。我们说如果没有线性函数出现在所有乘法门中（直到乘法常数），则简单秩是线性形式在中出现的秩。[DS 05]的拟多项式时间算法是基于一个最小的简单的具有有界顶扇入和计算零点的可积可积电路的秩是“小”的结果正式地说，结果是：定理2.1. (thm 1.4 [DS05]）。 设k≥ 3，d≥ 2，C ∈ 0是一个单极小如果是一个d次电路，有k个乘法门和n个输入，则rank（C）≤ 2 O（k）log（d）k−2。实际上，这意味着如果我们有这样一个电路，并且k是一个常数，那么我们可以在O（drank（C））=2O（log（d）k−1）的时间内，在r为零或不为t的情况下计算c k。这是找到一个3CCΣΣ∈·CC多项式时间算法，如果我们可以将rank（）的上限提高到常数（即与d无关）。实际上，[DS05]证明了rank（）=O（k）。这里我们给出一个与这个猜想相矛盾的恒等式因此，[DS05]的方法不太可能给出有效的算法，我们在第3节中给出了解决该问题的新技术在描述“大”秩恒等式x1，. . . ，x m是输入变量。对于i∈[m]，定义S i={x j1 + x j2 +. . . + x ji |1 ≤ j1<。. . d，我们得到= T1+ T2+ T3=0/F2. 很容易看出，它也是简单的和最小的，并且有2m−1次。2.2我们的算法在本节中，我们将概述我们的算法。输入是计算F[x1，x2，· · ·，xn]中的多项式的电路C。让C=T1+T2+···+Tk其中每个Ti是线性形式的乘积Ti=Li1Li2···Lid并且其中每个Iij是线性形式：Lij=aij1x1+aij2x2+···+aijnxn，aij1，aij2，···，aijn∈F4···YC.k= 2的情况：在这种情况下，我们需要验证T1=−T2但现在环F[x1，x2，···，xn]是唯一分解整环，线性形式是F[x1，x2，···，xn]中的不可约元素，因此两个多项式相等当且仅当lhs上的线性形式与rhs上的线性形式一一对应，且lhs上的任何一个单项式的系数等于rhs上的该单项式的系数这可以很容易地在确定性多项式时间内检查这解决了k= 2的情况。k= 3的情况：通过丢弃所有项的共同线性形式，我们可以假设T1，T2和T3互质。让Ld=ef{Lij| 1 ≤i≤3，1 ≤j≤d}是所有不同的（直到常数倍数）线性形式的集合，出现在术语T1，T2和T3。我们接受当且仅当n∈L，C= 0（modl）注意环F[x1，···，xn]/（l）同构于F上的n−1元多项式环，因此也是唯一的因子分解整环。此外，假设l发生在T1，我们有C=T2+T3（模1）因此，C= 0（mod1）的验证归结为k= 2的情况现在n∈L，C= 0（modl）C =0（modl）l∈LC = 0（modRadical（T1T2T3））由多项式的ABC定理[Sto 81，Mas84]我们推出deg（Radical（T1，T2，T3））> d，从而我们可以推出= 0作为F[x1，x2，xn]的一个元素。这给出了k= 3的确定性多项式时间算法。不幸的是，多项式的ABC定理不能以期望的方式扩展到3项以上的和（见[Pal93]）。为了得到更大的k值的算法，我们推广了上述方法，并进行线性形式的模积。3该算法在本节中，我们给出一个确定性的多项式时间算法，用于测试给定的有界顶扇元的多项式算术电路是否计算零多项式。基本思想与定理2.2的证明中使用的相同这里，我们得到的多项式将在某个局部环R <$F上而不是在F上，但是我们可以证明F[z1，. . . ， zn]继续保持在R[z1，. . . ，z n]。具体而言，我们需要：1) 若f（z1，. . . ，zn），g（z1，. . . ，z n）|p（z1，. . . ，z n）则f·g |p在R.2) 如果f（z1，. . . ，zn）的最大值大于p（z1，. . . ，z n），则f（z1，. . . ，z n）|p（z1，. . . ，zn）n（z1，. . . ，zn）= 0。5MM······∈···nnn3.1本地环在这篇文章中，我们将研究一些特殊类型的环，称为局部环。 为了完备性，我们定义了局部环，并提到了它们的基本性质。我们请感兴趣的读者参考[McD74]以了解此类环的进一步性质。定义3.1.一个交换环R称为局部环，如果每个非单位元r ∈ R是幂零的，即存在一个整数t≥1使得rt= 0。事实上，我们将考虑环R，它是某个域F上的有限维交换代数。在这种情况下，局部环R有唯一的极大理想M，它由所有的幂零元组成。而且每个元素r∈R都可以唯一地写成r=α+m，α∈F，m∈ M.这意味着存在唯一的环同态φ：R→F使得φ（α+m）=α。此外，如果R在F上的维数是d，则存在整数0≤td，<使得M的任何t个（不一定是不同的）元素的乘积在R中为零。局部环上多元多项式的性质在这一节中，我们将假设R是域F上的局部环，并且从R到F的唯一环同态是φ。映射φ可以自然的方式扩展为从R[z1，z2，，zn]到F[z1，z2，，zn]的同态。R的唯一极大理想是，t是R中使得t= 0的最小整数。我们想证明（多变量）局部环上的多项式具有类似于域上的多项式的一些性质引理3.2. 设R是局部环，p，f，gR[z1，z2， zn]是多元多项式，使得φ（f）与φ（g）互质. 此外，委员会认为，p0（modf）p=0（modg）则p=0（modfg）P roof. 设φ（f）和φ（g）的（总）度分别为f和g. 通过对变量z1，z2，···，zn应用一般情况下，zdf的系数不会损失，zdgR. 因此，在本发明中，zdf+dg的系数也是一个单位。现在把f和g看作一个变量zn的多项式，系数来自R [z 1，z 2，· · ·，z n −1 ]的分数环现在由于φ（f）和φ（g）在F上互质，它们也是函数域F（z1，z2，···，zn−1）上zn中的一元多项式因此，存在a，b∈F（z1，z2，···，zn−1）使得：aφ（f）+bφ（g）= 1 over F（z1，z2，···，z n−1）.即aφ（f）+bφ（g）= 1 in（R/M）（z1，z2，···，zn−1）。 利用著名的Hensel提升引理，我们得到存在a∈ R（z1，z2，···，z n−1），使得af + bg= 1 over（R/Mt）（z1，z2，···，z n−1），即R（z1，z2，···，z n−1）。6nn···∈······−j=1k=1• ⟨ ⟩≥现在通过引理的假设p0（modf）对于R[z1，z2，···，zn−1][zn]中的某个q，p=fq，p<$0（modg）fq⇒a/100(modg）的在R（z1，z2，· · ·，zn−1）[zn]在R（z1，z2，· · ·，zn−1）[zn]中的<$q<$0（modg）对于R（z1，z2，· · ·，zn−1）[zn]中的某个h，由于fg中zn的首系数在R中，p在R[z1，z2，···，zn−1][zn]中，因此通过高斯引理，我们得到事实上h∈R[z1，z2，· · ·，zn−1][zn]，因此在R[z1，z2，· · ·，zn]中p≠ 0（modfg）引理3.3. 假设p，f R[z1，z2，，Zn]，并且p具有总次数d。 此外，f总次数DJ>d，并且包含至少一个次数dj的单项式，其系数为单位，R.则在R [z1，z2，· · ·，zn]中p <$0（mod f）<$p = 0.证据由于p≠0（modf），我们有p= fg，其中g ∈ R [z1，z2，···，zn].通过对变量z1，z2，，zn进行适当的线性变换，如果需要，我们可以假设f中ZDJ的系数是R的单位。现在把p，f，g看作环R[z1，z2，，zn1]上zn中的一元多项式，设g关于zn的次数为t。那么rhs上的zdJ+t的系数是非零的，而lhs上的所有项的度数都至多为d d dJ。如果以下递归调用都返回YES，则输出ID. <$σ1（Ti）<$i∈[k]\{π1}，<$l11···l1e1，. . . ，lm1···lmem，σ1（s11. . . s1f1）..ID. <$σ BJ（Ti）<$i∈[k]\{πBJ}，. l11···l1e1，. . . ，lm1···lmem，σ BJ（sBj1. . . s BJfBJ）3.3正确性证明我们继续使用上一小节中的符号此处的索赔概述如下：定理3.4. ID（T1，. . . ，Tk ，0）如果fT1+···+Tk=0，则返回YES。最后，所花费的时间是poly（n，dk）。P roof. 不是所有递归调用都是ID（T1，. . . ，T，T0）使得ID（·，·）第一参数的大小减一，第二参数的大小增一，因此m k。因此，如果h（k）表示ID（T1，. . . ，T k，l11l1e1，. . . ，lm1l mem），则我们有以下递归：h（k）≤BJ·h（k−1）+poly（n，dm）≤（d+1）·h（k−1）+poly（n，dk）让9我.Σ≥{···} ∈···.ΣII1Bi∈[kJ]因此，我们得到h（k）=poly（n，dk）。为了显示输出的I D（T1，. . . ，Tk ，0）是正确的，我们提供了ID（ID1，. . . ，T k，l11···l1e1，. . . ，l m1···l mem）通过对k的归纳：权利要求3.4.1. ID（ID1，. . . ，T k，l11···l1e1，. . . ，l m1···l mem）返回YES，如果T1+···+Tk= 0（mod 111···11e1，. . . ，l m1···l mem）。第3.4.1章证据归纳的基本情况是当k = 1时，由步骤二 、在 这 种 情 况 下 ， T1 可 以 写 成f （ x1 ， . . . ， xm ） ·F （ xm+1 ， . . . ， xn ）使 得 当F∈R[xm+1，···，xn]时，f∈ R具有高次单项式（inxm+1，... . . ，xn）的解。显然，在R中T1=0当且仅当f=0（mod）。这可以通过展开f（x1，. . . ，xm），因为展开将最多具有dm项，所以我们可以在时间poly（dm）中进行。现在我们假设k =2，并且对于小于k的值，这个结论成立.如果所有的线性形式都发生在T1，. . . ，T k在R中，那么在第3步中，我们只需展开T i，并检查其和是否为零（modI）。 否则，在步骤4中，我们收集最大数量的线性形式（可能重复）s11，. . .，s1f1，，sB1，. . .，s BfB，使得对于所有i [B]，s i1s，如果i出现在某个T j中，并且多项式{s11···s1f1，. . . ，s B1···s BfB}在R回想一下，dJ是T1的最大度数。 . . ，Tk是R[xm+1，. . . ，xn]。在步骤4中，如果我们没有“足够的 f1+。. . + f B= dJ则观察到在（T1+. . . + T k）为：i（x1，. . . ，xm）xsf1···sfB因此，对于 T1+。. . + T k为零（mod），则i [kJ] g i必须为零（mod），这可以在时间poly（dm）中检查。如果它消失了，那么我们有：度（T1+. . . + Tk）为R上的多项式，则

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