非交换多项式身份测试和复杂性问题的自动机理论方法

1非交换和交换多项式恒等式检验诉Arvind，Partha Mukhopadhyay和Srikanth Srinivasan数学科学C.I.T Campus，Chennai 600 113，India{arvind，partham，srikanth}@ imsc.res.in摘要利用自动机理论的思想，我们设计了一个新的有效的（确定性）身份测试的非交换多项式身份测试问题（首次介绍和研究[RS05，BW05]）。更准确地说，给定一个非交换电路C（x1，···，xn）作为输入，计算一个多项式，F{x1，···，xn}的d次多项式，其中变量xi是非交换的，我们给出- 确定性多项式同一性测试，其检查C是否为0并且在d，n中的时间多项式中运行，|C|和t.同样的方法也适用于黑箱设置：给定一个d次非交换的黑箱多项式f∈F{x1，···，xn}，具有t个单项式，我们实际上可以在n，d和t的时间多项式中重构整个多项式f。实际上，我们将这个思想应用于黑箱非交换代数分支程序的重构（Nisan在[N91]和Raz-Shpilka在[RS 05]中考虑的ABPs假设黑盒模型允许我们查询ABP在任何给定门的输出，那么我们可以在确定性多项式时间内重建（等效）ABP最后，我们转向交换身份测试和探索的复杂性的问题时，输入多项式的系数来自一个任意的有限交换环与统一的元素被统一编码为字符串和环的操作是由一个预言。我们表明，多项式身份测试领域的几个算法的结果也举行时，系数来自这样的有限环。1介绍域上的多项式恒等式检验（PIT）是一个研究得很好的算法问题：给定一个运算电路C计算域F上F[x1，x2，···，xn]中的多项式，问题是确定C计算的多项式是否恒为零。当输入多项式f只通过黑盒访问时，也研究了这个问题即我们可以在Fn或F′n中的任何一点对F的域扩张F′求值。当f是由一个电路给出的问题是在随机多项式时间。甚至在黑盒设置中，当|F|适当地大于deg（f），则问题是在随机多项式时间内。一个主要的挑战是获得确定性的多项式时间算法，即使是限制版本的问题。Impagliazzo和Kabanets [KI03]的结果表明，该问题与prov一样困难。超多项式电路下界。事实上，即使对于深度为3的算术电路，该问题仍然是开放的，其输出为无界的双稳态门[DS05，KS07]。如Nisan [N91]所示，非交换代数计算更容易证明，界限。Nisan利用秩参数证明了计算非交换永久或非交换代数分支程序的非交换公式（和非交换代数分支程序）的arXiv：0801.0514v1 [cs.CC] 2008年12环F{x1，···，xn}中的行列式多项式，其中xi是非交换变量。因此，在非对易环境下的同一性检验也应该更容易，这似乎是合理的。事实上，Raz和Shpilka在[RS05]中已经表明，对于非交换公式（和代数分支程序），存在用于多项式恒等式测试的确定性多项式时间算法。然而，对于非对易电路，情况有些不同。 Bogdanov和Wee在[BW 05]中利用Amitsur-Levitzki定理证明了多项式阶非交换电路的恒等式测试是在随机多项式时间内进行的。基本上，Amitsur-Levitzki定理允许他们从矩阵代数Mk（F）中随机分配元素给非交换变量xi，其中2k超过电路的次数。本文的主要贡献是利用自动机理论的思想来设计新的高效（确定性）的多项式身份测试的非交换多项式。 更精确地说，给定一个非交换电路C（x1，···，xn）计算一个d次多项式，其中F{x1，···，xn}中有t个单项式，其中变量xi是非交换的，我们给出了一个确定性多项式恒等式检验，检验C是否为0且在d中的时间多项式中运行，|C|、n和t。在我们的算法的主要思想是把非交换单项式的xi作为词，并设计有限自动机，使我们能够区分不同的词。然后，利用自动机、幺半群和矩阵环之间的联系，我们能够确定性地为非交换变量选择相对少量的矩阵赋值来决定C是否为0。因此，我们可以避免使用Amitsur-Levitzki定理。事实上，使用我们的自动机理论方法，我们可以很容易地证明Amitsur-Levitzki的（较弱的）版本，这对于[BW 05]中的算法目的来说已经足够好了。我们的方法实际上是在黑盒设置中工作的事实上，给定一个d次非交换的黑盒多项式f ∈F{x1，···，xn}，它有t个单项式，我们可以通过给xi分配矩阵来计算它，我们可以在n，d和t的时间多项式中重构整个多项式f。此外，我们还将这一思想应用于黑箱非交换代数分支程序。我们扩展了Raz和Shpilka [RS05]的结果，给出了黑盒非交换代数分支程序的一个有效的确定性重建算法（其中我们只允许查询ABP的输入变量设置为多项式维数的矩阵）。我们的黑盒模型假设我们可以查询ABP的任何门的输出，而不仅仅是输出门。我们现在激励和解释的文件中的其他结果。最近，在[AM07]中，我们研究了PIT（通常的交换变量设置）及其与多项式理想隶属度问题的联系。虽然理想的成员资格是EXPSPACE完全的，但这两个问题之间有一个有趣的相似之处这是本文的动机 设I ∈ F[x1，···，xn]是由多项式g1，···，gr∈ F[x1，···，xk]和f ∈ F[x1，···，xn]生成的理想. 我们观察到f ∈ I当且仅当f在环F[x1，···，xk]/I[xk+1，···，xn]中是独立零的. 当系数环为F[x1，···，xk]/1时，本文证明了多项式恒等式检验的有效性. 因此，系数环F[x1，···，xk]/I的恒等式检验是EXPSPACE困难的，即使多项式f被显式地给出为单项式的线性组合。这就提出了多项式环R[x1，···，xn]的PIT的复杂性问题，其中R是具有单位元的交换环.复杂度如何依赖于环R的结构？本文对这一问题给出了一个精确的回答。我们证明了R的代数结构并不重要。R的元素具有多项式大小编码就足够了，并且w.r.t.可以有效地执行这种编码环操作。这与环F[x1，···，xk]/I相反：我们在F[x1，···，xk]中有双指数数量的多项式次数的元素，并且F[x1，···，xk]/I中的环运算本质上是理想隶属问题，因此计算困难。更确切地说，我们研究有限交换环R的多项式恒等式测试，其中我们假设R的元素被一致编码为{0，1}m中的字符串，其中两个特殊字符串编码0和31，并且通过对环预言机的查询来执行环操作。2非交换多项式恒等式检验回想一下，域F上的算术电路C定义如下：C以一组不定元（可交换或不可交换）和来自F的元素作为标量作为输入如果f，g是加法门的输入，那么输出将是f+g。类似地，对于乘法门，输出将是fg。对于不可交换的变量，电路遵循乘法的顺序如果每个门的扇出最多为1，则算术电路是公式Raz和Shpilka在[RS05]中以及Bogdanov和Wee在[BW05]中研究了非交换同一性检验在Bogdanov-Wee的论文中，他们考虑了F{x1，···，xn}上的小次多项式f，对于域F，由算术电路给出他们能够给出一个随机多项式时间算法的身份测试的f。他们算法的关键特征是从非交换身份测试减少到交换身份测试，这是基于Amitsur和Levitzki的经典定理[AL 50]。代数的最小恒等式Raz和Shpilka [RS05]通过首先将齐次公式转换为非交换代数分支程序（ABP）（如[N91]中所做），给出了非交换公式身份测试在这一节中，我们研究了非交换多项式恒等式检验问题。利用自动机理论的简单思想，我们设计了一个新的确定性身份测试，如果输入电路是稀疏的，小的程度，在多项式时间内运行。我们的算法只使用黑盒访问非交换多项式，我们甚至可以有效地重建多项式。我们将首先描述的算法来测试，如果一个稀疏多项式的多项式次数在noncommuting变量是同为零。然后我们给出了一个算法，重建这个稀疏多项式。虽然后一个结果包含了前一个结果，但为了说明清楚，我们对两者都进行了描述。此外，我们注意到，我们可以假设多项式是作为域F上的算术回路给出的。在交换变量的情况下，[OT88]给出了一个插值算法，该算法计算给定的稀疏多项式，因此可以用于身份测试。目前还不清楚如何将该算法推广到非交换的设置。我们的身份测试算法评估给定的多项式在特定的，精心选择的点在矩阵代数（多项式维度的基本字段），这样任何非零稀疏多项式保证评估为非零矩阵在这些点之一。重建算法使用上述同一性测试算法作为基于前缀的搜索中的子例程，以找到所有单项式及其系数。我们现在非正式地描述身份测试算法。我们的想法是将每个单项看作一个短的二进制字符串。因此，稀疏多项式由这样的字符串的多项式数（以及相应单项式的系数）给出。该算法分两步进行;在第一步中，我们构造一个有限自动机的小集合，使得给定短二进制字符串的任何小集合，集合中至少有一个自动机接受该集合中的一个字符串;在第二步中，对于每个构造的自动机，我们在F上的矩阵代数上构造一个点元组，使得元组中的任何单项“模仿”自动机上相应字符串的运行。现在，考虑到非零多项式f的小次数与几项，我们保证已构建了一个自动机A'隔离'的字符串从收集的字符串对应的然后，我们证明了在对应于A的元组上对f求值会给我们一个非零输出：因此，我们可以得出f非零的结论。我们现在正式描述这两种算法。42.1预赛我们首先回顾一些标准的自动机理论符号（例如，见[HU78]）。 设有限自动机A=（Q，δ，q0，qf）在{0，1}n 中 输 入 字 符 串. Q是A的状态集，δ：Q×{0，1}→Q是函数的转移，q0和q分别是唯一的和唯一的状态集（但我们只考虑具有唯一接受状态的自动机）。 对于每个字母b ∈ {0，1}，设δb：Q → Q是由下式定义的函数：δb（q）= δ（q，b）。这些函数生成从Q到Q的所有函数的幺半群的子幺半群。这是自动机A的转移幺半群，在自动机理论中得到了很好的研究：例如，参见[Str94，第55页]。 我们现在定义0 - 1矩阵Mb∈ F|Q| ×|Q|如下所示：.1 如果δ（q）= q′，Mb（ q，q′）=B0否则，请执行以下操作。矩阵Mb是函数δb的图的邻接矩阵。由于Mb的元素只有0和1，我们可以认为Mb是任何域F上的矩阵。此外，对于任意w=w1w2· · ·wk∈ {0，1}<$，我们定义矩阵Mw为矩阵乘积Mw1Mw2· · · Mwk.如果w是空字符串，则定义Mw为维数的单位矩阵|Q|×| Q|.对于字符串w，让δw表示转移函数到w的自然扩展;如果w是空字符串，δw是恒等函数。很容易检查：Mw（ q，q′）= .1如果δw（q）=q′，（一）0否则。因此，Mwisalsoamatri xofzerosandonesforanystringw. A是0，Mw（q0，qf）=1if，且只有1yifw被自动机A所接受.2.2自动机上电路的输出现在，我们考虑域F上具有非交换变量x1，···，xn的多项式环F{x1，···，xn}.设C是计算多项式f∈F{x1，···， xn}的非交换算术电路.设d是f的次数的上界。我们可以把非对易变量x1，···，xn上的单项式看作是长度为n的字母表上的字符串。对于我们在2.3节中的构造，在字母表{0，1}中对变量xi进行编码是方便的。我们通过用字符串vi=01i0对变量xi进行编码来实现这一点，这基本上是一种带有分隔符的一元编码显然，xi上的每个次数最多为d的单项式LetA=（Q，δ，q0，qf）是在相等的相位{0，1}上的一个有限积分。当我们看到一个人的时候，|Q| ×|Q|有矩阵Mvi∈F，如2.1节中定义的，其中每个vi是编码的二进制字符串xi. 我们感兴趣的是当电路C的输入xi被矩阵Mvi代替时得到的输出矩阵。 这个输出矩阵的定义很明显：输入是|Q|×| Q|矩阵，并且我们在每次加法时进行矩阵加法和矩阵乘法（分别为：乘法）的电路C. 我们将C在自动机A上的输出定义为输出矩阵Mout。显然，给定电路C和自动机A，矩阵Mout可以在时间上计算poly（|C|、|一|，n）。我们观察到以下性质：A上C的矩阵输出M完全由多项式f由C计算;电路C的结构是无关的。 这对我们来说很重要，因为我们只对f感兴趣。特别地，当f = 0时，输出总是0。更具体地说，考虑当C计算一个只有一项的多项式时会发生什么，f（x1，· · ·，xn）=cxj1· · ·xjk，其中系数c ∈F.在这种情况下，输出矩阵Mout5KX一一我显然是矩阵cMvj1···Mvj=cMw，其中w=vj1···vjk是表示m ono m ia lxj1···xjk. 因此，通过E-1a-obovee，我们发现当A拒绝s时，整数Mut（q∈0，qf）为0w，当A接受w时，c。一般来说，假设C计算多项式f=tcimi，其中t为非零条款，其中 ci∈F\ {0}和 mi= QDIj=1ij得双曲余切值.di≤d。让 wi=vi1···vidi=1表示二进制字符串表示单项mi。最后，设Sf={i ∈ {1，···，t} |A接受wi}。定理2.1给定任意算术电路C计算多项式f∈F{x1，···，xn}和任意有限A=（Q，δ，q0，qf），则输出MoutC在A上是这样的，（q0，qfΣ）=i∈Sf 克岛证据证明是一个简单的结果的定义和性质的矩阵Mw规定第2.1节。 注意，M=f（M ，· · ·，M）的。 但f（M ，· · ·，M）= scM 得双曲余切值.出来v1vnv1vni=1i wiwi=vi1···vid是一个双结构的字符串表示形式。由E方程1，我们知道Mwi（q0，qf）如果wi被A接受，则为1，否则为0加起来，我们就得出了结果.现在我们解释自动机A在测试C计算的多项式f是否为零时的作用 我们的基本思想是尝试和设计一个自动机A，它只接受一个词，从所有的词中，有一个词被传递到非零运算器中。这就证明了Mout（q0，qf）是滤除的单项的非零系数。 更确切地说，我们将主要以下面的形式使用上述定理，我们将其作为推论陈述。推论2.2给定任意算术电路C计算多项式f∈F{x1，···，xn}和任意有限代数A=（Q，δ，q0，qf），则输出MutofConA是f：(1) 如果将每个字符串都弹出以在f中进行单次删除，则Mut（q0，qf）=0。(2) 如果A对f中的一个单项式进行了一次试探，则Mout（q0，qf）是f中该单项式的非零系数。此外，M_out可以在时间poly（|C|、|一|，n）。证据（1）和（2）都是上述定理的直接结果计算M的复杂性很容易从它的定义中得出。上述定理的另一个有趣的推论如下。推论2.3给定F{x1，···，xn}上的任意算术回路C，以及任意阶为dm的单项式m，我们可以计算C中m的系数在时间poly（|C|，dm，n）。证据应用推论2.2，其中A是任何标准自动机，它接受对应于单项式m的字符串，并拒绝所有其他字符串。显然，可以选择A，使得A具有唯一的接受状态，|一|时间复杂度O（n）注2.4观察推论2.3在交换设置F[x1，···，xn]中极不可能成立。因为，在交换的情况下，计算单项式x1···xn的系数，即使是线性形式的任意乘积，也至少和F上的永久问题一样困难，当F = Q时，F上的永久问题是P-完全的。我622注2.5推论2.2也可以用来独立证明引理A.4中陈述的Amitsur和Levitzki的结果的较弱形式。特别地，很容易看出域F上的d × d矩阵代数Md（F）不满足任何d次非平凡恒等式<。为了证明这一点，我们将把非交换单项式看作是直接在n个字母表{x1，· · ·，xn}上的字符串。 假设f= f tc m ∈ F{x，···，x}是一个d次非零多项式<. 显然，我们可以构建一个i=1i i1n在字母表{x1，···，xn}上的自动机B，它只接受f的一个字符串，即一个非零单项式，比如mi0，并拒绝{x1，···，xn}上的所有其他字符串。此外，B可以用最多d个状态来构造现在，考虑在B上计算f的任何电路的输出M。推论2.2输出矩阵是非零的，这证明了结果。2.3有限自动机我们从一个有用的定义开始定义2.6设W是二进制字符串的有限集合，A是二进制字母表{ 0，1 }上的有限自动机的有限族。• 我们说A对于W是孤立的，如果存在一个字符串w ∈ W和一个自动机A ∈ A，使得A接受w并拒绝所有w′∈ W \{w}。• 我们说A是（m，s）-隔离族，如果对于s个二进制串的每个子集W ={w1，···，ws}，每个二进制串的长度至多为m，存在A ∈ A使得A对于W是隔离的.固定参数m，s ∈N。 我们的第一个目标是构造一个（m，s）隔离的自动机族A，其中|一|A中每个自动机的大小都是多项式有界的。然后，结合推论2.2，我们将能够获得确定性的身份测试和插值算法在续集。回想一下，我们只处理具有唯一接受状态的有限自动机下面，对于字符串w ∈ {0，1}n，我们用nw表示由二进制数1w表示的正整数。对于每个素数p和每个整数i ∈ {0，···，p −1}，我们可以很容易地构造一个自动机Ap，i，它精确地接受那些w，使得nw <$i（modp）。此外，Ap，i可以被构造为具有p个状态和恰好一个最终状态。我们在A处对A进行的任何操作都是对Ap的选择，而A p是在运行的。我不想让你的第一个孩子素数，且i ∈ {0，· · ·，p−1}。 形式上，设N表示（m+2）s+1;A是Ap，i的集合，其中p遍历前N个素数，i ∈ {0，···，p −1}。 注意，根据素数定理，上面选择的所有素数的值都以N2为界，这显然是m和s的多项式。因此，我们认为，|= poly（m，s），且每个A ∈ A的大小由poly（m，s）界定。|= poly (m, s), and each A ∈ A isbounded in size by poly (m, s).在下面的引理中，我们证明，A是一个（m，s）-隔离自动机族。引理2.7如上定义的有限自动机A族是（m，s）-隔离自动机族。证据考虑任意s个二进制字符串W的集合，每个字符串的长度至多为m通过构造A，Ap，i∈ A孤立W当且仅当p对某些j和所有k j不整除nwj−nwk，且nwj<$i（modp）。显然，如果p满足这些条件中的第一个，则可以容易地选择i，使得满足第二个条件我们我将证明在前N个素数中有某个素数不能整除P=Qj/=k（nwj-nwk）。这是从他身上流下来的。如果数据库中的数据预处理数量或P的数据预处理数量太多，|P|，whichheiss由（m +2）s= N − 1明确界定。证明到此结束我们注意到，上面的（m，s）-隔离族A可以清楚地在时间poly（m，s）中构造。72.4身份验证算法我们现在描述身份测试算法。 设C是计算F{x1，···，xn}上的多项式f的输入电路。设t是f中单项式个数的上界，d是f的次数的上界。和2.2节一样，我们将x1，···，xn上的单项式表示为二进制串。f中的每一个单项式都由一个长度不超过d（n +2）的字符串表示。我们的算法如下进行：使用第2.3节的构造，我们计算一个族A，自动机，使得A对任何集合W是孤立的，其中至多t个字符串的长度至多为d（n +2）。对于每个A ∈ A，该算法计算A上C的输出M。 如果对于任何A，Mouti= 0，则该算法得出结论，由输入电路计算的多项式不等同于零;否则，该算法声明多项式等同于零。上述算法的正确性几乎是直接从推论2.2得出的。如果多项式为零，很容易看出算法输出正确答案。如果多项式是非零的，那么通过构造A，我们知道存在A ∈ A，使得A恰好接受对应于f中单项式的字符串之一。那么，根据推论2.2，C在A上的输出是非零的。因此，该算法正确地推断出计算的多项式不等同于零。至于算法的运行时间，很容易看出自动机族A可以在时间poly（d，n，t）上构造。此外，每个A的矩阵Mvi（所有矩阵的大小为poly（d，n，t））可以在多项式时间内构造。因此，整个算法在时间上运行poly（|C|，d，n，t）。我们证明了以下定理：定理2.8给定任意算术电路C，如果C计算一个d次多项式f∈F{x1，···，xn}，其中至多有t个单项式，我们可以在时间上检验poly（|C|，d，n，t），如果f等同于零。特别地，如果f是稀疏的并且是多项式次数的，那么我们有一个确定性多项式时间算法。在任意非交换算术电路的情况下，[BW 05]给出了恒等式检验问题的一个随机指数时间算法他们的算法基于Amitsur-Levitzki定理，该定理迫使恒等式测试为非交换变量随机分配指数大小的矩阵，因为电路可以计算指数阶多项式。然而，请注意定理2.8给出了一个确定性指数时间算法，但有一个附加的限制，即输入电路计算一个至多有指数数量单项式的多项式。一般来说，指数次数的多项式可以有双指数数量的项。2.5非交换多项式我们现在描述一种算法，它有效地计算输入电路给出的非交换多项式。 设C、f、t和d如2.4节所示。设W表示f中系数为非零的单项式所对应的所有字符串的集合。对于所有二进制字符串w，设Aw表示任何接受w并拒绝所有其他字符串的标准自动机对于任何自动机A和字符串w，我们让[A]w表示接受A接受的那些字符串的自动机，此外，包含w作为前缀。 对于有限自动机集合A，设[A]w表示集合{[A]w|A ∈ A}。我们现在描述一个子程序Test，它以算术电路C和一组有限自动机作为输入A并返回一个域元素α ∈F。子程序Test将具有以下性质：（P1）如果A对W是孤立的，对应于f中单项式的字符串集合，则α/= 0。8出来(P2)在特殊情况下，|一|=1，并且上述成立，则α实际上是孤立单项式的系数。(P3)如果没有A ∈ A接受W中的任何字符串，则α=0。我们现在给出测试（C，A）的简单描述：对于每个A ∈ A，子例程Test计算输出矩阵MAC在A。 如果有A ∈ A使得MA（qA，qA）0，那么对于第一个这样的自动机A ∈ A，Test返回标量出来 0fα=MA（qA，qA）。这里，注意qA，qA表示自动机A的初始状态和最终状态。如果出来 0f0f如果没有找到这样的自动机A ∈ A，则子例程返回标量0。从推论2.2可以直接得出，检验具有性质（P1）-（P3）。此外，明确测试2016年05月05日05：05：05| C|、||一||），其中||一||表示A中自动机的大小之和。设f∈F{x1，···，xn}表示由输入电路C计算的非交换多项式.我们现在描述一种基于递归前缀搜索的算法Interpolate，该算法将电路C和二进制字符串u作为输入，并计算f的所有包含u的单项式（以及它们的系数当使用我们的编码xi<$→ vi=01i0编码为字符串时，作为前缀。显然，为了得到f的所有单项式及其系数，只要用u=0，空字符串，运行这个算法就足够了在下文中，设A0表示在第10节中构造的（m，s）-隔离自动机族{Ap，i}。2.3，参数m=d（n+2）和s=t。如2.3节所解释的，我们可以在时间上计算A0poly（d，n，t）。假设f是由电路C计算的多项式。我们现在描述算法形式上插值（C，u）（算法1）。从Test子程序和引理2.7的正确性可以清楚地看出该算法的正确性要限制运行时间，请注意算法从不对字符串u调用Interpolate，除非u是某个对应于单项式的字符串的前缀因此，算法调用Interpolate至多O（td（n+2））个前缀u。 以来||[A0]u0||和|一个u|对于所有前缀u，都由poly（d，n，t）限定，因此算法的运行时间是poly（|C|，d，n，t）。我们在下面的定理中总结了这个讨论定理2.9给定任意算术电路C计算次数至多为d的多项式f ∈ F{x1，···，xn}，且最多具有t个单项式，我们可以在时间poly（|C|，d，n，t）。特别地，如果C计算多项式次数的稀疏多项式f，则f可以在多项式时间内重建。3非交换变量上代数分支程序的插值在本节中，我们研究黑盒代数分支程序（ABP）计算非交换环F{x1，···，xn}中的多项式的插值问题。我们在黑盒设置中输入ABP（定义如下）P，我们的任务是输出计算相同多项式的ABPP作为P.为了使任务在黑盒设置中可行，我们假设我们可以在任何情况下评估P中间的门。我们首先观察到，第2节中的所有结果在输入多项式f只允许黑盒访问的假设下成立。在非交换的设置中，我们将假设黑盒访问允许对来自基域F. 这里隐含的是，评估的成本在矩阵的维度上是多项式的。 注意9算法1插值算法一曰： 过程插值（C，u）2：α，α′，α′′←0。3：α ←Test（C，{Au}）<$Au是只接受u的标准自动机4：如果α=0，则5：休息。u不能对应于f的单项6：其他7：输出（u，α）。u是系数为α的f的单项式的二进制编码8：如果结束现在，该算法找到所有单项式（以及它们的系数）包含u0或u1作为前缀的二进制编码。9：如果|u|= d（n +2），则10：停止。11：其他12：α′←Test（C，[A0]u0），α′′←Test（C，[A0]u1）.13：如果结束14：如果α′/= 0，则15：插值（C，u0）。在C中有一些单项式扩展u016：如果结束17：如果α′′/= 0，则18：插值（C，u1）。在C中有一些单项式，扩展u119：如果结束20：结束程序10i=1一这是一个合理的非交换黑箱模型，因为如果我们只能在F或F的任何交换扩张上对f求值，那么我们就不能区分由f表示的非交换多项式和相应的交换多项式。我们在下面陈述我们的结果的黑盒版本定理3.1（类似于定理2.1）给定黑盒访问任何多项式f=tci mi ∈F{x1，···，xn}和f在A=（Q，δ，q0，qf）的情形下，A的输出M是有界的ΣM（ q，q）=c，其中Sf={i |1 ≤ i ≤ t且A接受对应于m的字符串w}出来 0fi∈Sfi Ai这里多项式f在A上的输出定义类似于2.2节中电路在A上的输出。推论3.2（类似于推论2.3）给定对F{x1，···，xn}中多项式f的黑盒访问，以及任何次数为dm的单项式m，我们可以计算f中m在时间poly（dm，n）中的系数。最后，定理3.3（类似于定理2.9）给定对F{x1，···，xn}中次数至多为d且单项式至多为t的多项式f的黑盒访问，我们可以在时间poly（d，n，t）中计算f的所有单项式及其系数。特别地，如果f是多项式次数的稀疏多项式，则它可以在多项式时间内重建。我们的插值算法的非交换ABPs的动机Raz和Shpilka我们的算法使用第2节（主要是推论3.2）中提出的思想逐层插值给定的定义3.4 [N91，RS05]代数分支程序（ABP）是一个有向无环图，其中一个顶点的入度为零，称为源，一个顶点的出度为零，称为汇。图的顶点被划分为编号为0，1，···，d的级别。 边只能从第i层到第i +1层，i∈ {0，···，d − 1}。 源是级别0上的唯一顶点，汇是级别d上的唯一顶点。每个边被标记为输入变量的齐次线性形式ABP的大小是顶点的数量请注意，在i和i+1层上两个顶点u和v之间没有边的ABP等价于从u到v的边标记为零线性形式的ABP。因此，不失一般性，我们假设在给定的ABP中，相邻层上的每对顶点之间都有一条边如前所述，我们将假设对输入ABPP的黑盒访问，其中我们可以在F上的任意矩阵环上的任何门处评估由P计算的多项式。为了指定我们想要输出的门，我们用层号和门号（在层中）索引P的门基于[RS 05]，我们现在为ABP的水平i定义Raz-Shpilka基设第i层的节点数为Gi，并且设{p1，p2，···，pGi}为在节点处计算的多项式我们将用Gi× ni矩阵Mi来识别这组多项式，其中Mi的列由ni个不同的i次单项式索引，行由多项式pj索引。 矩阵Mi的元素是相应的多项式系数。Raz Shpilka基是生成整个列空间的Mi的至多Gi个线性无关列向量的集合注意，基由单项标识。在该算法中，我们需要在ABP的每一层计算一个Raz-Shpilka基注意，在0级，计算这样的基是微不足道归纳地假设我们可以在i层计算这样的基。用Bi={v1，v2，· · ·，vki}表示基，其中vj∈FGi，且ki≤Gi. 假设，11MS该基对应于单项式{m1，m2，...，mki}。 我们通过计算Mi+1中单项式{mjxs}j∈[ki]，s∈[n]的列向量，然后从中提取线性无关向量，从而在i+1层上计算RazShpilka基. 计算这些列向量需要计算这些单项式的系数，这可以用推论3.2在多项式时间内完成。注意，我们也知道这个基的元素对应的单项式现在我们正式描述插值算法如前所述，我们将逐层构造输出ABPP′，使得P′的每个门计算与P中相应门相同的多项式。显然，这个任务在0级是微不足道的。假设我们已经完成了id层的施工。我们现在构造第i+1层。这只涉及计算水平i和水平i+1之间的线性形式。因此，在第i层的Raz-Shpilka基中有ki≤Gi个设对应于这些向量的单项式为B={m1，···，mki}。将任意门u固定在P中的第i+1层，并设pu为P中该门处的多项式计算。显然，pu=阿努格岛j=1pjj其中P是在级i处的第j个门和U处的第j个门之间的用于LA的链路。我们有，pu==阿努格岛j=1阿努格岛j=1pjjΣm：|M|= I-是的c（j）m卢恩s=1Σa（j）xsΣΣGi=mxsc（j）a（j）m：|M|= i，sΣ=m：|M|= i，sMsj=1mxs cm，a s其中c和a分别表示域元素（c（j））和（a（j））注意到表示m s m j s j s我们需要计算的未知向量在上面的等式中，每个单项式mxs给我们一个关于as的线性约束。然而，这个约束系统的规模是指数级的为了获得一个可行的解决方案，{as}s∈[n]，我们观察到满足仅对应于单项式mxs的约束就足够了其中m ∈ B。所有其他约束条件都是这些约束条件的简单线性组合，因此自动对这些问题的任何解决方案都感到满意现在，对于m ∈ B和s ∈ {1，···，n}，我们使用推论3.2的算法计算m xs在pu中的系数和m在每个pi中的系数。因此，我们有所有的线性约束，我们需要解决{as}s∈[n]。首先，注意这样的解是存在的，因为黑盒ABP P中的线性形式给出了这样的解。此外，这个线性方程组的任何解在门u处生成相同的多项式pu。因此，我们可以使用这个线性方程组的任何解作为我们的线性形式。 我们在第i +1级对所有门u执行此计算。迭代的最后一步是计算水平i +1的Raz-Shpilka基。12JKJK我们可以用归纳法来证明算法的正确性从输入黑盒ABPP，对于每一层k，设Pjk，1≤ j ≤Gk表示由P计算的代数分支程序，输出门为层k中的门j.假设，作为归纳假设，该算法已经计算了直到第i层的所有层的线性形式，而且，该算法对于直到第i层的所有层都有正确的Raz-Shpilka基。这给了我们一个重建的ABPP′，直到水平i，具有以下性质，对于1≤k≤i，每个ABPP′，1≤ j ≤Gk计算与对应的Pjk，1≤ j ≤Gk相同的多项式，其中通过指定k级的门j为输出门，从P′获得在这个归纳假设下，很明显，我们的插值算法将计算级别i和i+1之间的线性形式的正确集合。因此，该算法将正确地重建一个ABPP′，直到第i+1层，以及该层对应的Raz-Shpilka基。现在我们可以用下面的定理来概括这个结果定理3.5设P是F{x1，x2，···，xn}上大小为s，深度为d的ABP，由黑盒访问给出，允许对从矩阵代数Mk（F）中选择的输入xi对P的任何门求值，其中k的值多项式有界。 然后在确定性时间poly（d，s，n）中，我们可以计算ABP P′，使得P′的值与P的值相同。4非交换恒等式测试与电路下界在第二节中，我们给出了一个新的非对易多项式的确定性恒等式检验，它对多项式有界次数的稀疏多项式在多项式时间内运行。然而，真正感兴趣的问题是由小次数非交换电路给出的多项式的恒等式测试，Bogdanov和Wee[BW 05]给出了有效的随机化测试。当非对易回路是公式时，Raz和Shpilka [RS05]证明了问题是在确定性多项式时间内的。他们的方法使用了Nisan的非对易公式下界技术[N91]的思想对于多项式次数的电路，证明非交换PIT是确定性多项式时间有多难在可交换的情况下，Impagliazzo和Kabanets [KI03]已经表明，去随机化PIT意味着电路下界。这意味着NEXP/PARP/poly或整数Permanent都没有多项式大小的算术电路。我们观察到这个结果在非对易情形下也成立。也就是说，如果非对易PIT具有确定性多项式时间算法，则NEXP/PARP/poly或非对易Permanent函数不具有多项式大小的非对易电路。如前所述，在某些情况下，非交换电路的下界比交换电路的下界更容易证明Nisan [N91]已经给出了非对易公式大小的指数大小下界，并且对于纯非对易电路[N91，RS 05]，进一步的结果是已知的然而，证明一般非交换电路计算永久的超多项式大小下界仍然是一个悬而未决的问题。非交换永久函数Perm（x1，···，xn）∈ R{x1，···，xn}定义为：ΣYnPerm（ x1，· · ·，xn）=σ∈ Sni=1xi，σ（i），其中系数环R是任何具有单位元的交换环具体来说，对于下一个定理，我们选择R= Q。P13定理4.1如果多项式次数C（x1，···，xn）∈ Q{x1，···，xn}的非对易回路的PIT是确定性多项式时间的，则NEXP/PARP/poly或非对易永久函数都不具有多项式大小的非对易回路。证据假设NEXP是一个多项式。然后，根据[IKW02]的主要结果，我们有NEXP = MA。此外，由户田现在，假设多项式次数的非交换电路的PIT是在确定性多项式时间内，我们将证明，（非对易）永久函数没有多项式大小的非对易回路。相反，假设它确实有多项式大小的非对易回路。显然，我们也可以用它来计算此外，如在[KI03]中，我们注意到非交换的n× n永久也唯一地由恒等式p（x）<$x和p（X）=<$ix p（X）刻画，其中1i≤n，<1ij=11j i−1j其中X是i2个非交换变量的矩阵，Xj是它的第j个子式w.r.t.第一排即 如果任意多项式pi，1 ≤ i ≤ n在非对易变量xij，1 ≤ i，j ≤ n上满足这n个恒等式当且仅当pi计算非对易变量的i × i不变量.其余的证明就像Impagliazzo-Kabanets [KI03].我们可以很容易地描述一个NP机器来模拟一个P-P-Z计算。NP机器在m× m矩阵上为Perm猜测一个多项式大小的非交换电路，其中m是查询矩阵大小的多项式界。然后NP通过检查它必须满足的m个非交换恒等式来验证电路计算了永久式。这可以通过假设在确定性多项式时间内完成。最后，NP机器使用电路来回答所有的整数永久查询。把它们放在一起，我们得到NEXP=NP，这与非确定性时间层次定理相矛盾。5有限环在这一节中，我们将Schwartz-Zippel引理推广到有限交换环上，并将其应用于R[x1，···，xn]中黑盒多项式的恒等式检验，其中R是具有单位的有限交换环，其元素由来自{0，1}m的字符串一致编码，其中特殊字符串e表示单位，并且环运算由环预言机执行。我们回忆一些关于有限交换环的事实[B74，AM69]。有单位元的交换环R是局部环，如果R有唯一的极大理想M。一个元素r ∈ R是幂零的，如果对某个正整数n，rn = 0. 一个元素r∈ R是一个单位，如果它是可逆的。即 对于某个元素r′∈ R，rr ′ = 1。有限局部环的任何元素要么是幂零元，要么是单位元。 理想I是R的素理想，如果ab ∈ I蕴涵a ∈ I或b ∈ I。对于有限交换环，素理想和极大理想重合。 这些事实大大简化了有限交换环的研究（与无限环相反）。有限环R的根记为Rad（R），定义为所有幂零元的集合，即Rad（R）={r ∈ R| {n>0 s.t rn= 0}根Rad（R）是R的一个理想，如果R是局部环，则它是唯一的极大理想。设m表示最小正整数，使得对每个幂零r ∈ R，rm=0，即（Rad（R））m=0.设R是任意有单位元的有限交换环，{P1，P2，··