非交换模型多项式身份检验算法

非交换模型中的确定性多项式恒等式检验兰·拉兹魏茨曼科学以色列雷霍沃特ran r az@wisdom. 我是一个人。梭IlAmirShpilka<$ DEAS，哈佛大学麻省理工学院马萨诸塞州剑桥amirs@de a s. 哈哈哈。埃杜乌摘要我们在以下两种情况下给出了多项式身份测试的确定性多项式时间算法：1. 非交换算术公式：该算法得到非交换变量x1，...，xn，并确定公式的输出是否相同为0（作为形式表达式）。2. 纯算术电路：该算法得到一个纯算术电路作为输入（由Nisan和Wigderson [3]定义），变量为x1，...，并且确定电路的输出是否相同为0（作为形式表达式）。对于Nisan [2]定义的非交换代数分支程序，我们给出了一个确定性的多项式时间恒等式检验算法一个应用是深度为3的多线性算术电路的确定性多项式时间身份测试。最后，我们观察到一个指数下界的永久性和行列式的纯算术电路的大小。(Only纯电路深度的下限以前是已知的[3]）。[1]部分工作是在作者担任普林斯顿高等研究院成员时完成这项研究得到了以色列科学基金会的支持。†由国家安全局（NSA）和高级研究与发展活动（ARDA）根据研究办公室（ARO）合同编号支持DAAD 19 -01-1-0506。11介绍设F是一个域，C是一个算术电路，输入变量为x1，...，xn，在域F上。输出C（x1，.，xn）因此是环F [x1，...， xn]。可以确定这个多项式是否同为0吗？1Schwartz和Zippel证明了如果f∈F [x1，.，xn]是与0多项式不同的d次多项式，并且c1，...，cn∈F在D种可能性中随机一致选取，则f（c1，.， cn）= 0，概率至多为d/D [6，4]。这给出了一个非常有效的概率过程来测试算术电路的输出是否相同为0。 一个突出的开放问题是找到一个等效的确定性过程，在多项式时间内（在电路的大小）运行。在本文中，我们感兴趣的非交换的情况下，其中的输入变量的电路C是非交换的。输出C（x1，.，xn）因此是环F{x1，...， xn}的多项式在非交换变量x1，...， xn. 请注意，任何算术电路都可以在交换变量上进行评估，以获得F [x1，...，xn]，以及在非交换变量2上，以得到F{x1，.，xn}。在某些情况下，当对交换变量进行评估时，电路的输出同样为0，而当对非交换变量进行评估时，电路的输出同样为非零。另一方面，如果输出在非交换变量上相同为0，那么它在交换变量上也肯定相同为0因此，输出在非交换变量上相同为0的事实可以用作它在交换变量上相同为0的证明如果电路中每个门的扇出最多为1，则算术电路称为公式。我们的主要结果是一个确定性的多项式时间算法的身份测试的算术公式在非交换的情况下。该算法得到一个算术公式作为输入，并确定当对非交换变量求值时，公式的输出是否相同为0。我们还给出了一个确定性的多项式时间算法的身份测试，所谓的纯算术电路（首先定义的Nisan和Wigderson [3]）。 粗略地说，纯算术电路是变量集合X1，...，如果T1是门v 1的输出所依赖的变量集合的集合，T2是门v2的输出所依赖的变量集合的集合，则T1<$T2或T2<$T1或T1<$T2=<$（对于电路中的每两个门v1，v2）。我们的研究结果的一个应用是确定性的多项式时间算法的身份测试的深度为3的多线性算术电路。该算法得到一个深度为3的多线性算术电路作为输入，并确定该电路的输出是否相同为0（在标准交换情况下）。请注意，同一性检验等同于等效性检验，例如，给定两个多项式f、g，确定f是否=g。 在理论计算机科学的许多研究领域中，进行有效的等价性测试的能力是计算模型的一个非常理想的属性。具有有效等价性测试的计算模型的一个示例是OBDD（限制顺序有界决策图），并且这可能是OBDD流行的原因之 一1请注意，有两种不同的方式来解释这个问题。首先，我们可以问输出作为一个函数是否等于0。在本文中，我们感兴趣的是第二种解释：是电路的输出同等于0作为一个形式表达？(that是，输出是环F[x1，...，xn]）。然而，请注意，如果多项式的次数小于字段的大小，则相同为0的两个概念是等价的。2这里我们假设电路中每个乘积门的输入都是有序的。2在许多研究领域。在这里，我们给出了比OBDDs强的计算模型的确定性等价性检验。特别地，我们给出了所谓的非交换算术分支程序（如Nisan [2]所定义的）的确定性等价性测试。请注意，非交换算术分支程序比OBDD更强大。1.1方法我们的方法是非黑盒方法。也就是说，我们使用电路的结构，而不是将其用作评估输出多项式的黑盒。我们使用以前用于证明算术电路的非交换模型的下界的工具和方法[2，3]。Nisan证明了如果f ∈ F{x1，...， xn}是由一个小的算术公式计算的，那么由f的所有偏导数所张成的空间是小维的[2]。在这里，我们展示了如何递归地检查是否所有这些偏导数都相同为0。在纯电路的情况下，由所有偏导数构成的空间不是小维数的。尽管如此，由所有偏导数的某些子集所张成的空间仍然是小维的。如前所述，我们展示了如何递归地检查这些子集中的所有偏导数是否都相同为0。非交换算术公式的大小和纯算术电路的深度的下界是已知的[2，3]。Impagliazzo和Kabanets最近的一个结果表明，确定性多项式恒等式测试和证明电路大小的下界之间存在紧密联系[1]。特别是，Impagliazzo和Kabanets证明了算术电路大小的强下界意味着请注意，对于本文中讨论的模型而言，这些保留值并不适用于非复杂模型，并且这些保留值也不适用于在这里，我们使用开发的方法来证明某些类的下界，直接给出这些类的确定性多项式时间的身份测试。在本文之前，纯算术电路的大小没有下限。为了完成这幅图，我们证明了这样一个下界。我们展示了一个指数下界的永久性和行列式的纯算术电路用偏导数的方法很容易得出下界，但以前不知何故被忽略了。1.2组织第二节给出了非交换算术公式的多项式恒等式检验算法在第三节中，我们给出了纯电路中多项式恒等式测试的一个算法。在第4节中，我们证明了这些算法也给出了多线性深度为3的递归电路的恒等式测试。在第5节中，我们陈述了纯电路的下界。下限的证明在附录A中。2非交换算术公式2.1预赛在这一节中，我们给出了一个多项式时间的确定性算法，以确定由非交换公式给出的多项式是否恒为零。令X ={x1，...，xn}是我们的变量集。算术公式是一棵二叉树，它的边指向根。树的叶子用输入变量或字段元素标记任何内部顶点都标记为3算术运算{+，×}之一。每一条边都用我们工作的领域中的一个常数来标记。用算术运算+标记的节点v，其子节点是v1和v2，计算多项式α1P（v1）+α2P（v2），其中P（vi）是在vi处计算的多项式，αi是标记v和vi之间的边的常数（类似地，当v被标记为×）。公式的输出是在根处计算的多项式。公式的大小是树的节点数。我们考虑这个模型的一个变种-非交换算术公式。 设F{x1，.， xn}是域F上以非交换变量x1，. . . ，xn.也就是说，在F{x1，...， xn}的形式表达式xi1·xi2·. . . ·xik和xj1·xj2·。. . ·xjl相等当且仅当k= l且lil= jl（而在多项式的交换环中， 即使我们置换其变量，任何单项式也保持相同，例如x1·x2= x2·x1）。非交换算术公式是在环F{x1，.，xn}。由于这个环中的两个多项式不一定可交换，我们必须在每个乘法门中区分左子和右子。请注意，每个多项式都可以通过非交换公式计算。给定一个非交换公式，我们可以在交换区域上计算它。在[2]中，Nisan证明了把可积公式推给可积公式的非交换公式的长度的指数下界. N的 一 个 分 支 是 从 非 交 换 公 式 到 代 数 分 支 程 序 的 一 个 分 支 。代数分支程序（ABP）是一个有向无环图，其中一个顶点的入度为零，称为源，另一个顶点的出度为零，称为汇。图的顶点被划分为编号为0，...，D. 边缘可以仅从级别i到级别i +1，其中i = 0，.，d− 1。 源是级别0上的唯一顶点，汇是级别d上的唯一顶点。每个边都用输入变量中的齐次线性形式标记ABP的大小是顶点的数量由ABP计算的多项式是从源到汇的所有有向路径上标记该路径边的线性函数的乘积的和。注意代数分支程序是计算的交换模型，但我们将感兴趣的是N个N个N ，xn}。特别地，如果宿-源路径的边缘是e1，...，ed，其中ei介于水平i− 1和水平i之间，并且i（X）是标记ei的线性函数，那么我们取乘积的顺序为1（X）·. . ·ddd（X）显然，具有d+1个水平的ABP计算d次齐次多项式。对于ABPA的两个顶点v1，v2，使得v1在层i1中，v2在层i2和i1

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