新的多项式族类VPSPACE与实数上的多项式时间并行求解决策问题的复杂性

−VPSPACE与实数Pas al Koiran and Sylvain PerifelLIP？普通人吗里昂河畔[Pas al.Koiran，Sylvain.Perifel ens-lyon.fr2018年9月阿布斯特拉湾本文介绍一种新的多项式族类VPSPACE。粗略地说，多项式族在VPSPACE中，如果其可以在多项式空间中计算元素。 我们的主要定理是：如果（一致的，无常数的）VPSPACE族可被有效地求值，则可在实数上用多项式时间并行求解的决策问题的类PARR收敛到PR。因此，首先必须能够表明存在难以评估的VPSPACE家族，以便将PR从NPR，甚至从PARR分离。关键词：计算复杂性，代数复杂性，Blum-Shub-Smale模型Valiant的模型1产品介绍在代数复杂性理论中研究了两类主要的问题：求值问题和判定问题。评价问题的一个典型例子是评价矩阵的积和式，众所周知，积和式族对于容易定义的多项式族的类VNP是完备的[21]。判断多元多项式是否有实根是判断问题的一个典型例子。这个问题在Blum-Shub-Smale模型中是NP完全的。本文的主要目的是提供一个传递定理，评估和决策问题的复杂性。因此，本文与[13]的精神相同在那篇论文中，我们证明了，如果某些多项式然后，某些决策问题变得容易一些。[13]中所考虑的多项式是在某个域K上的多项式的指数形式的多项式，这些多项式易于计算（精确定义见[13]）。正在考虑的设计问题是在结构（K，+，，=）中属于NP的那些，其中不允许乘法。在本文中，我们使用了更大的一类多项式族，我们都是VPSPACE。粗略地说，一个多项式族（可能是指数次数的）在VPSPACE中，如果它的元素可以用多项式计算CNOUMR5668 ENS Lyon，CNRS，UCBL，INRIA.arXiv：cs/0610009 v2 [cs.CC] 2007年22Pas al Koiran和Sylvain Perifel斯帕湾本文首先证明了多元多项式方程组的结式构成一个VPSPACE族.我们的主要结果是，如果（uniform，无常量）VPSPACE系列可以进行有效评估，然后PARR类的决策问题，可以解决的并行多项式时间在实数下降到PR。这个结果主要依赖于Grigoriev [11]中的一个组合引理，特别是依赖于[7]中建立的等价形式。类PARR在实数上的计算理论中扮演的角色与PSPACE在离散复杂性理论中扮演的角色大致相同。特别地，它涉及NPR[1]（但这一点的证明比在本文中更复杂）。从我们的主要结果可以得出，为了将PR与NPR，或者甚至从PARR，必须首先能够证明存在VPSPACE很难评价的家庭。这似乎是一个非常具有挑战性的下限问题，但它仍然可能比证明永久性难以评估更容易。文件的组织第2节记录了一些概念和符号，代数复杂性（Valiant模型，Blum-Shub-Smale模型）。类VPSPACE在第3节中定义（在均匀和非均匀设置中），作为一个例子，我们在第3.3节中表明多元多项式系统的结式形成（均匀）VPSPACE族。不需要阅读第3.3节来理解本文的其余部分。VPSPACE的一些不确定性在第3.4节中给出在第4部分中，讨论了VPSPACE系列易于评估的假设。证明了（假设广义黎曼假设）这个假设等价于：VP=VNP和P/poly=PSPACE/poly.恩琼-这两个等式的关系是一个非常强的假设：根据[3]的结果(see[12]，它意味着，再次假设GRH，NC/poly=PSPACE/poly。这平等的原则显然仍然与我们目前的不足相一致，复杂性理论的立场。我们还讨论了VPSPACE家族易于评估这一假设的统一、无常量版本事实证明，这个更强的假设意味着PSPACE会退化为NC的多项式时间统一版本。这种复杂性的戏剧性崩溃看起来极不可能，但就我们所知，它不能用复杂性理论的现有方法来反驳。最后，本文的最后两部分致力于转移定理。第五节讨论符号条件，这是计算实代数几何的一个重要工具。转移定理在第6节的开头陈述，并在其后证明。2预赛我们使用的布尔复杂性理论的概念是相当标准的。本文主要讨论代数复杂性。{}− × ≤∈0| |R≤-×{−×}∈ ∈⇔是一致机，我们将使用代数的家族理论来继续[19]。-×VPSPACE与实数上的一个转移定理32.1Blum-Shub-Smale模型与布尔复杂性不同，代数复杂性处理的是其它结构，比0，1。本文主要研究实数的序域（R，+，）虽然Blum，Shub和Smale[2，1]的原始定义r_∞是R上的语言的集合，即R~ ∞的子集=n≥0Rn.代数图1是一个有向图，其顶点称为门，有0、1或2个整数。输入门是入度为0的顶点输出门是输出度为0的门。我们假设在电路中只有一个SUH门。入度为2的门由来自集合+，，的符号标记。入度为1的门，称为测试门，标记为0？.图C的大小，用符号C表示，是图的顶点数。具有n个输入门的电路计算从Rn到R的函数。在输入u时，根据定义，电路返回的值等于其输出门的值。门的值按通常的方法定义即，输入门号i的值等于第i个输入ui.其他门的值然后被递归地定义：对于+门，它是它的条目的值的总和，对于-门，它是它们的距离，对于-门，它是它们的乘积。如果测试门的入口值>0，则测试门取的值为0，否则取1我们假设输出是测试门，不失一般性因此，iruit返回的值是0或1。类 PR是语言L<$R∞的集合，满足存在一个元组a<$∈Rp（n的索引p<$nt）和一个P-一致的多项式大小的单元族（Cn），满足下列条件：Cn有n+p个输入，且对任意x<$Rn，x′LCn（x<$，a<$）=1。P-一致条件是指Cn可以用普通的（离散的）图灵机构造成n中的时间多项式. 注意这一点说明了[1，2]中机器人的作用。在[6]中， PARR类是R上的语言集合，一个PSPACE-一致的代数单元族，其深度为多项式（可能为指数整数），且对于PR具有常数a′。最后请注意，我们也可以设计一个类似的没有onstans的lasses。 我们将使用后缀0来表示这些无常数的lasses，例如P0和PARR。2.2Valiant模型在Valiant的模型中，人们计算多项式而不是重新识别语言。因此，我们用算术单元代替代数单元。这本书的长度治疗，可以在[3]中找到。算术运算与代数运算相同，但不允许使用测试门 也就是说，我们有不定式x1，。. . ，xu（n）作为输入，与R的任意常数一起;有+，和-门，因此我们计算多元多项式。算术运算器所计算的多项式是由它的输出门所计算的多项式以通常的方式定义的。因此，一族（Cn）算术运算可计算一族（fn）多项式，fn∈ R[x1，. . . ，xu（n）]。|| ≤0¬ − ∧ ∨ −| |VP族的总和。更优选地，如果存在（gn（x<$，y<$））∈ VP，则（fn（x<$））∈VNP{}→{}4 Pas al Koiran和Sylvain Perifel在[15]中定义的类VPnb是由多项式大小的算术单元的族（Cn）计算的p多项式的族（fn）的集合，即， Cn计算fn，存在多项式p（n），使得Cnp（n）对所有n成立.我们将不失一般性地假设变量的数量u（n）由n的多项式函数限定。该文件指出，没有与Valiant的原始类VP不同，Valiant的原始类VP需要多项式的次数上的约束请注意，这些定义是不统一的。通过在向量上增加多项式时间一致性条件，得到类一致VP_nb， 家庭，如第2.1节。类VNP是由指数定义的多项式族的集合。和一个多项式p，|是的|=p（n）且fn（x∈{0，1}p（n）gn（x）.我们 也禁止 从我们的arithmeti iruits在无界-degree lasses，and de ne免费的姑娘唯一的 目前允许的是1（为了允许常数多项式的计算）。至于姑娘们 在设计问题中，我们将使用超级脚本0来指示例如，我们将写VPnb（对于有界度的lasses，我们要更加小心;见[15]）。最后请注意，算术单元至少与布尔单元一样强大在这个意义上，一个人可以用前者来模拟后者。的确，我们可以用1u代替u，用uv代替u， v+v 紫外线这证明了下面的Lassi al引理。引理1. 任何布尔函数C都可以用一个大小不超过3C的算术来模拟，在这个意义上，在布尔输入上，两个函数都输出相同的值。3VPSPACE类3.1定义我们x一个任意的e ∈K。VPSPACE的定义如下所述：α1αu（n）的 OE 有趣。 一个单项式x1· · ·xu（n） 以二进制形式表示为α=（α1，. . . ，αu（n）），将e写成x′α。定义1. 设（fn）是一族具有整数元的多元多项式. （fn）的因子是函数a，其在输入（n，α，i）上的值是f n中单项式x <$α的因子的第i位a（n，α，i）。 Fur-thermorere，a（n，α，0）是单项式x′α的 极 限 的 符号。因此fn可以写成fn（x<$）= - 是的（−1）a（ n，α，0）αΣi≥1Σa（n，α，i）2i−1x<$α.这个函数是一个函数a：0，1-0，1，因此可以被看作是一种语言。这使我们能够谈论的复杂性的原函数。∈0×000VPSPACE和实数上的一个转移定理50定义2. 类均匀VPSPACE是所有族（fn）的集合，多元多项式fnK[x1，. . . ，Xu（n）]满足以下要求：1. 变量的个数u（n）是多项式有界的;2. 多项式fn具有整数项;3. 对于某个多项式p，fn的元素的大小有界于2p（n）;4. 对于某个多项式p，fn的次数有界于2p（n）;5. （fn）的原函数在PSPACE中。0我们有霍森德第一个统一的VPSPACE，一个统一的女孩没有由于这是本文的主要研究对象。然而，为了与Valiant所设定的传统保持一致，在Se tion 3.5中定义的类VPSPACE是不均匀的，并且允许任意的常数。3.2另一种特征化设Uniform VPAR0为 多项式族类 由一个PSPACE-一致无常数多项式深度算术0(and可能是指数大小）。这在很大程度上破坏了Uniform VPSPACE。提案1. UniformVPSPACE和Uniform VPAR这两个类是相等的。证据设（fn）是一致VPSPACE族.为了用多项式深度的算术运算来计算fn，我们并行地计算它的所有单项式，并以除法和加法的方式求和。由于（fn）上的一致性条件，所得到的arith-meti环族是一致的.相反，取多项式深度的算术公式我们表明我们可以建立一个多项式深度的布尔函数，它以单项式的编码α作为输入，并计算x′α的o e。我们通过推导，计算出原算法中每个门的x′α的有效是的。对于输入门，这很容易。对于一个+-门，OE是的。对于门ab，我们并行计算cd的和，单项式x<$β和x<$γ满足β+γ=α，其中c是x <$γ在门a中的输出，d是x<$β在门b中的输出。 整个边界条件保持一致，且具有多项式深度。因此，平行计算的命题在PSPACE中起着积极的作用。⊓⊔我们在这里看到了与PARR的相似性，根据定义，PAR R是由多项式深度的统一代数单元重新识别的那些但是，在均匀VPSPACE的算法中，当然没有测试门。3.3例代数几何是从计算的观点研究多项式的一个自然的例子源。对于instan e，Hilbert多项式∈J/D≥n0波恩+1.Σ变量由p的元素列表编码。olynomials，即，通过矩阵Macδ（f1，. . . ，fn+1）则被定义为6 Pas al Koiran和Sylvain Perifel[4]从离散复杂性理论的角度研究了这里我们研究一个不同的例子：多元多项式系结式的计算。 一个n + 1个复变量的n +1个齐次方程组 有非平凡解当且仅当其结式为零。我们给出下面的结式的结构。More details an befound for instan e在[14]或[5]中。设f1，. . . ，fn+1C[X0，. . . ，Xn]是n +1个齐次多项式组。 结式存在于两个矩阵M和M ′的行列式的商中：第MR=detM′（1）其中M的元素在f的元素中，M′是M的一个子矩阵.矩阵M被称为Maulay矩阵（Sylvester矩阵对于两个单变量多项式的推广）并且被描述如下。设di为度fi和d= 1 +i=1（di− 1）。 用Mond表示中所有单项式的集合，X0，. . .，Xn的次数d：Mon d的矢是N =D+nD矩阵M具有N行和N列，都由Mond. 对单式x′α的回归表示多项式x′α迪伊其中i=min{j;xdj 整除x′α}。最后，子矩阵M′存在于M的行和列中，这些行和列没有减少，参见[5]。我们要计算的不是结果R本身，而是它的倍数，即detM。当detM ′=0时，如果我们只考虑R的为零，这不会改变任何东西。从现在开始，为了简单起见，我们假设所有的di都相等。我们将让n在nity中变化，但di的通常值δ将保持不变。系统（f1，. . . ，fn +1）的n +1个δ次齐次多项式k（ n+ 1）个变量（a1，1，.. . ，a1，k，a2，1，.. . ，an+1，k），其中 k=n+δδ是数字n +1个变量中δ次单项式的集合。注意，k是n中的多项式，任何固定δ。n.Σ（f1，. . .，fn+1）。这个矩阵的大小为n+d，其中d=1+（n+1）（δ− 1）。这是n的指数函数。 计算M的行列式可以通过深度多项式的一个公式，在M的大小，因此多项式在n.以上的思考证明了下面的命题。2号提案 对于任何xedδ，家庭（det（Macδ））（行列式n+1元n +1次δ次齐次多项式组的Ma aulay矩阵）在一致VP空间中 。同样地，（1）中矩阵M′的行列式构成一致VP空间0家人.X0000VPSPACE和实数上的一个转移定理73.4封闭性质下面的引理是 学习命题1。引理2. 统一VPSPACE在巨额和巨额的产品面前迷失。我们 甚至可以在一个集合上求和和乘积，{0，1}，如以下引理中所证明的。引理3. Let一Be 一 语言 在PSPACE，（fn（x<$，y<$））a 家庭 在0对于VPSPACE和p（n）是一个多项式，|是的|=p（n）。然后家人（gn（x<$））和（hn（x<$））定义如下：gn（x<$）= Σn∈A=p（n）fn（x<$，n<$）和hn（x<$）=Yn∈A=p（n）f n（x′，x′）.证据 使用引理2就足够了，Σn∈A=p（n）fn（x）=Σn∈{0，1}p（n）χA（x'）fn（x'，x'），以及Yn∈A=p（n）fn（x）=Yn∈{0，1}p（n）[χA（）fn（x）+（1−χA（））]，其中，χA， 由引理1证明A的原证明函数在一致VP空间中命题1 sin e A是由一个具有p多项式深度的布尔环族所确定的。⊓⊔3.5非均匀类VPSPACE现在让我们定义非均匀的lassesVPSPACE00VPSPACE的。注意0VPSPACE与的一致性OE有趣。统一的VPSPACE是非统一的定义3. 类VPSPACE是所有多元多项式fn∈ K[x1，. . . ，xu（n）]满足以下要求：1. 变量的个数u（n）是多项式有界的;2. 多项式fn具有整数项;3. 对于某个多项式p，fn的元素的大小有界于2p（n）;4. 对于某个多项式p，fn的次数有界于2p（n）;5. （fn）的幂函数是PSPACE/p。现在，类VPSPACE是多元多项式的所有ll族（fn（x<$））的集合，0函数fn∈K[x1，. . . ，xu（n）]，则re存在一族（gn（x<$，y<$））∈VPSPACE与一个常量元组族（a<$（n））结合起来，对于aln，满足：f n（x<$）=gn（x<$，a<$（n））.B∈B−B我我我BBy2zvi，j对于逆，取一个族（fn）∈VPSPACE：记住它是一个8 Pas al Koiran和Sylvain Perifel我们暂时介绍了一个有界度的VPSPACE版本：这将被证明是有用的比较VPSPACEVP和VNP在这最后两个多项式的次数lasses是多项式有界的。一个家庭（fn）多项式在VPSPACE0中，如果（fn）VPSPACE0和元素以及fn的次数是多项式有界的。 LassVPSPACEB然后从VPSPACE0中定义，定义方式与从定义3中的VPSPACE0这个新的lass对于我们的目的来说是有趣的，因为下面的两个引理。引理4.VPSPACE b= VP空间VPSPACE = VP nb。证 据设 rst ， VPSPACE =VPnb ， 取 一 个 族 （ fn ） ∈ VPSPACEb. SineVPSPACEb∈VPSPACE，（fn）通过假设在VPnb中成立.若（fn）的次数是多项式有界的，则（fn）∈ VP.be表示为fn（x<$）=gn（x<$，a<$（n）），对于某些情况0a<$（n）和（gn（x<$，y<$））∈VPSPACE。 为 因此，让我们将gn的u（n）变量重命名为：v1，.. . ，vu（n），因此我们有：gn（v<$）= - 是的（1）a（n，α，0）α2名残疾人（n）i=1Σa（n，α，i）2i−1v<$α，其中，a以PSPACE/poly表示。 在这个表达式中，p（n）是一个p多项式，并且2p（n）限制了元素的大小以及g n的次数。为了使用假设，我们必须以某种方式定义一个族（hn）∈VPSPACE0，模拟（gn）。Let us de ne.Σhn（ z1，1，.. . ，z1，p（n），z2，1，.. . ，zu（n），p（n），w1，.. . ，wp（n）），其中直观地，变量zi，j是在gn和wi中，值22.更正式地，hn定义如下：Qrepla evkingnbyj∈Jk zi，j，其中集合Jk包括设置为1在k的二进制表示中;i−1102p（n）i−1Q代替了gnby的项i=1a（n，α，i）2中的oe ent2j∈ Ji−1wj，其中集合Ji−1包含二进制中设置为1的位表示i-1。然后，hn的次数是多项式有界的，并且所有元素都在-1，0和1。进一步注意，初始函数仍然在PSPACE中。因此（hn）∈VPSPACE0，因此（hn）∈ VP通过假设。它仍然需要补充J我我 和wiby22证明（gn（v<$）=gn（x<$，y<$））∈VPnb，然后证明replaéy⊓⊔引理5. VPSPACE包含VNP。J0∈⊕⊆⊆VPSPACE和实数上的一个转移定理9证据 设（HCn）为下式定义的族：HCn（ x1，1，.. . ，x1，n，x2，1，.. . ，xn，n）=ΣYnxi，σ（i）σi=1其中，对{1，. . . ，n}。该多项式计算由其邻接矩阵给出的图中Hamiltony的个数。（HCn）是VNP-完全的，参见[2 1]或[1 5]。 如果VPSPACEb在p-条件下失，且仍保持HCn，则引理如下。⊓⊔4关于VPSPACE有小圈的假设在这一部分中，我们研究了假设VPSPACE=VP nb和Uniform VPSPACE 0= Uniform VP nb。3号提案 在广义黎曼假设（GRH）下，VP nb= VPSPACE多项式[P/poly = PSPACE/poly and VP = VNP]。此外，即使没有GRH，从右到左的含义也成立。证据 假设P/poly = PSPACE/poly且VP = VNP 。 根据引理4，等式VPSPACE=VPnb 等 价 于 度 有 界 的 类 比 VPSPACEb=VP 。 设 （ fn ）VPSPACEb：它的原函数在PSPACE/p中，我们假定它在P/p中. 在VNP族的任意函数的集合上P/poly（见[3]），其中P/poly，（fn）在VNP中是fat。 根据我们的假设，它是VP。对 于 逆 ， 现 在 假 设 VPSPACE=VPnb 。 同 样 ， 这 等 价 于VPSPACEb=VP。根据引理5， 还有待证明的是，PSPACE/poly中的语言A在fat中延伸为P/poly。A由一个p多项式深度布尔元的P/poly-一致族表示，根据引理1和命题1，存在一个族（fn）∈VPSPACE，使得在一个ny布尔元输入x∈{0，1}n上，fn（x<$）∈{0，1}，f n（x<$）=1当且仅当x<$∈A。通过我们的假设，（fn）∈VPnb，从而存在一族多项式大小的算术iruits（Cn），具有任意常数，计算（fn）。为了为了用布尔型ir uits在布尔型输入上评估这些ir uits，现在的任务是消灭敌人。 我们在[3]中提出了要求。设y<$e为函数Cn的初值，所有gn（X<$，Y<$e）为yCn计算的多项式，其中由新变量Y′代替初始值。我们gn（X<$，y<$）=fn（X<$），因此方程组S在Y中由y定义.¯ΣS=gn（x<$，Y）=fn（x<$）x<$∈{0，1}n有一个解决方案，你对C。该系统中的所有方程都是整数，对于某个多项式q，其次数以2q（n）为界，权以22q（n）为界，其中多项式的权是其元素的绝对值之和.nq（n）≤F≤≤−00∈Uniform VPSPACEPSPACE10 Pas al Koiran和Sylvain Perifel根据[3]中的定理4.4，假定GRH存在一个素数，2p2满足S在上有解p.的确存在苏阿帕阿尽快π（a）时间复杂度O（n）>1log（wa），其中d和w分别是方程的次数和权的界，π（a）是素数的个数a. 有一个多项式大小的arith，计算多项式gn（X<$，y<$′）的Fp方法及该多项式在两个输入上取与fn（X<$）相同的值。注意p的大小是p多项式，并且这个系统S over Fp的解y ′ ′也有多项式大小。 因此，一个多项式大小的布尔运算模型可 以 很 容 易 地 计 算 gn（X<$，y<$′）在Fp上的值. 这个booiruit在布尔输入上具有与fn相同的值。当eA∈P/poly时，公布结果。⊓⊔现在我们把下一个命题转到假设的最统一的版本，它比命题3的版本更强。为了证明，我们需要[16]和[15]中的两个定义。定义4. 算术运算C的形式度是其输出门的形式度，其中门的形式度是递归定义输入门的形式度为1;+门或-门的形式度是其输入的形式度的最大值;×门的形式度是其输入的形式度之和。定义5. 类VP是多项式族的集合计算人多项式形式次数的无常数（即仅使用1作为常数）多项式大小的代数的族。下面的命题类似于命题3，但在统一的集合中，并且没有假设广义黎曼假设。这不是lear0 0在这个命题，是否假设一致VPnb=一致VNPnb，假设一致VP0=一致VNP。0 04号提案Uniform VPnb=Uniform VPSPACE当且仅当0 0P= PSPACE和Uniform VP nb = Uniform VNP nb。0 0证据假设rstP=PSPACE且Uniform VPnb=Uniform VNPnb。采取0a 家庭（FN）它的主要功能是，当在P假设。因此，单项式与它们的元素的和是0 0在统一VNPNB.因此，（fn）∈一致VPnb的假设。对于逆，让我们首先证明P=PSPACE。设A是PSPACE语言：它是由一个统一的家庭多项式深度布尔ir-uits。利用引理1和命题1，我们得到了一类多项式∈0000⊕∈S00让 我们现在证明， CUP⊆P-均匀NC ， 的 假设VPSPACE和实数上的转移定理110（fn） UniformVPSPACE输入，即，与布尔值一致 ir uits on booleanf n（x<$）∈{0，1}且[fn（x<$）=1 <$$> x <$∈A].通过我们的假设，（fn）∈ Uniform VPnb，使得存在计算（fn）的多项式大小的一致算术单元族。当然，在布尔输入上，可以在多项式时间内对这些值进行计算（模2工作以避免溢出）。这意味着PSPACE= P。0 0现在我想， 的 证明 的 UniformVNPnb =Uniform VPnb 是李尔sin e0 0 0UniformVPnbUniformVNPnbUniformVPSPACE.⊓⊔0我们现在可以证明假设一致VPSPACE=统一VP编号5号提案统一VPSPACE0=均匀VPnb = P-均匀NC。证据 根据命题4，假设已经包含了P=PSPACE。UniformVPSPACE0= Uniform VPnb. 这足以说明，语言HamiltonPath（判断是否存在奇数的问题-b图中Hamilton路的一个特例（参见[18，p.448]）是P-一致NC的。一个图由其布尔adja en y矩阵（ai，j）给出（其中ai，j=1i，i和j之间有一条边），Hamilton路的数目为Σ1≤j k≤nΣσ∈Sj，knY−1i=1ai，σ（ i），其中Sj，k是从j开始到k结束的所有n-y条线σ n的集合（为了在图中计数路径，j不同于k，而不是y条线，并且为了不计数两条路径，j小于k，这将使HamiltonPath问题变得平凡化）。多项式Σpn（x1，1，.. . ，x1，n，x2，1，.. . ，xn，n）=乌斯怀亚-1xi，σ（ i）J K σ∈Sj，ki=1因此，输出布尔编码x 1，1上的Hamilton路径数。. . x1，nx2，1. . . xn，n的图G.这个多项式族（pn）很容易被看作是在一致的VP空间中，具有多项式有界的次数，并且它的模2求值提供了问题G ∈ N HamiltonPath？ .通过我们的假设，（pn）∈一致VPnb，使得存在一个P-一致计算（pn）的多项式大小的算术单元族（Cn）。我们将建立一个函数族（Dn），它计算一个多项式0（qn）∈VPsu h，在布尔输入上，pn和qn具有相同的奇偶性.注意尽管多项式在其次数上有界，（pn）不需要已经在−−−20用O（n2）个处理器，从而在P-均匀NC中规划了P-P./S12 Pas al Koiran and Sylvain Perifel0VP是因为Cn的形式次数不需要是多项式（实际上，是常数的指数大小可以由Cn计算）。这就是为什么我们不直接计算Cn与[16]的算法并行。这里的想法是， 一个只计算余数模2的因为我们只对模2的结果感兴趣。然后，从Cn构建Dn如下。首先，注意pn的次数为n−1。我们分别计算每个h齐次 分量：Cn的每个h门α被分成n-1个门α1，. . .，αn −1，门αi计算的是a的i。不计算0次齐次分量（即常量），只计算它们的模2余数。换句话说，我们用常数0代替偶数常数，用1代替奇数常数。P-均匀性保持不变，因为我们可以在多项式时间内计算常数模2. Dn的最后一步是计算齐次项输出门的组件。如何在每一步计算这些齐次分量，同时保持多项式的大小，这是容易的和众所周知的：我们只是忽略了次数>n1的齐次分量。利用这一结构，我们知道pn和qn是模2的整数，结构是P-一致的，并且由于结构中没有常数，Dn的形式度至多为n10我不想再这样了。当e（qn）∈VP.因此，为了确定Hamilton路径，我们只需计算在给定的输入上求qn模2的值，即求一个P-一致环多项式大小s（n）和多项式有界形式次数n1。定理[16]中的5.3告诉我们，通过logspa e，可以对suhairuitanb eeevaluatedmodulo 2-时间复杂度为O（log（s（n））log（ns（n），即O（log（n）2），然后，假设Uniform VPSPACE0的=一致VPnb我们已经证明2PSPACE= PP P-均匀NC。请注意，这个构造似乎不是对数均匀的，因为计算常数模2是一个P-完全问题。在构造一个多项式时间一致的迭代算法族时，也可以用[2 2]的结构代替[1 6]的并行算法. 事实上，正如[16]中所指出的，[22]的构造可以在多项式时间内完成。⊓⊔备注1. 尽管不太可能，但PSPACE=P-均匀NC的分离并不符合作者的知识（相反，由于空间层次定理，PSPACE可以从对数均匀NC中分离出来）。5签署条件5.1定义给定s多项式f1，. . .，fs∈Z[x1，. . .，xn]。一个符号条件仅仅是一个s-元组S ∈ {−1，0，1}。直觉上，S的第i个坐标代表∈n nn2VPSPACE和实数上的转移定理13fi的符号：−1表示<0，0表示0，1表示> 0。因此，一个poi ntx<$∈Rn的符号条件是元组S∈{−1，0，1}s，满足如果fi（x<$）<0，则Si = − 1，如果fi（x<$）=0，则Si = 0，如果fi（x<$）>0，则Si = 1。当然，有些符号条件是不可实现的，在这个意义上，多-nomials an nowhere take orresponding signals（think for instan e ofx2+ 1whi h an only take positive values overR）.我们说一个符号条件是满意的，如果它是某个x′的符号条件Rn和w都是满足符 号 条件的个数。在下一节中详细介绍的关键结果是，在所有可能的签名条件中，很少有令人满意的（即，N是小的），并且存在多项式空间算法来枚举它们全部。5.2符号条件下面的定理将被证明是我们证明中的一个中心工具。对满意的符号条件的数量的限制来自于N-Milnor限制[17]（参见Grigoriev[10，引理1]）;枚举算法来自于Renegar [20，Prop. 4.1英里定理1. 设f1，. . . ，fs∈ Z[x1，. . . ，xn]是最大次数的s个多项式D、谁的 元素的位大小≤L。然后又道：1. 存在N=（sd）O（n）个满意的符号条件;2. 有一个算法使用工作空间e（logL）[nlog（sd）]O（1），其中，在输入（f1，. . . ，fs）和二进制的（i，j），输出第j个第i个满意签名条件的组成部分。如果S是由这种枚举算法产生的第i个满足的符号条件，我们说S的秩是i（因此秩仅仅是符号O（1）O（1）O（1）枚举中的条件）。注意，如果d= 2，s= 2L= 2如ASE所示，则算法的工作空间是n中的多项式。5.3枚举所有可能测试的多项式在执行代数运算时，输入端x '处的某些多项式的值被测试为零。如果x和y对于所有可能测试为零的多项式具有相同的符号条件在执行过程中将是相同的。因此，我们可以处理符号条件（即布尔词）而不是代数输入。注意，为了找到输入x ′的符号条件，我们必须能够在多项式空间中枚举所有在代数运算中被测试为零的多项式。这是在[9]中完成的，Th。3英里。6号提案设C是深度为d的n元常数自由代数环。1. 在C的某些计算中，可能检验为零的不同多项式的个数为2dO（n）.−2R0R0R为了将P0问题转化为P-R问题，14 Pas al Koiran and Sylvain Perifel2. 存在一种使用工作空间（nd）O（1）的算法，其在输入C和二进制整数（i，j）上输出这些多项式的第i个的第j证据C是根据门的深度分层的：输入门在0级，输出门是唯一在d级的门。假设0到i1层的测试结果是固定的：我们可以计算在i层测试的所有多项式。由于我们的代数单元的扇入最多为2，所以在C的第i层上最多有2个d-i门：特别地，在第i层上最多有2个d-i多项式可以被测试。但是多项式在级别i计算的最多是2i，并且其大小元素是（nd）O（1）2i。因此，根据定理1，对于水平i的检验，最多有（2d）O（ n）个可能的最优解，而且它们在空间e（nd）O（1）中是可解的。因此我们一个计算所有第i层测试的所有可能的（2d）O（ n），并进行了individually proceed。这给出了一个算法，使用工作空间e（nd）O（1）来枚举所有可能被测试的多项式，是的。由于在每一层上有2dO（n）个可能的多项式，所以整个解（即d层）的多项式总数为（2dO（n））d=2dO（n），如命题中所述.⊓⊔注意，当我们的代数运算不是常量自由的时候，这个命题也是有用的：用新的变量替换常量就足够了。唯一的风险确实是采取更多的多项式到一个计数器，因为我们已经replaed特殊常数的generi变量。6一个转移定理在这一部分中，我们证明了我们的主要结果。0 0 0定理2. Uniform VPSPACE = Uniform VPnb = UniformPARR = P0.请注意，无常量类PARR到P0的塌陷意味着PARR到PR的塌陷：只需用新变量替换常量，以便将PARR问题转换为PARR问题，然后用它们的变量替换这些变量。0设A∈PARR：它由一致的常数自由代数族（Cn）所多项式深度的brai ir uits。对于onvenien e，我们xn并与Cn一起工作。对于定理2的证明，我们需要找到输入x ′的符号条件，其中p是多项式f1，. . . ，fs，也就是说 ， 对 于 在 C n 的 执 行 中 可以被测试为零的所有多项式，我们用N表示关于f1，. . . ，fs.请注意，大多数前面的结果取决于多项式f1，.. . ，fs，因此在Cn的hoi e上。 对于instan e，在e Cn和f1上，. . . ，fs是Hosen，满足的符号条件是固定的，我们将谈论第i个满足的符号条件，而不明确地涉及多项式f1，. . .，fs. 为了确定输入的符号条件，我们给出了一个多项式时间的算法来检验某个VPSPACE族是否为零。这里是形式化的一个多项式时间算法的概念与VPSPACE测试。0≤∈⇐⇒联系我们VPSPACE和实数上的转移定理150定义6.具有一致VPSPACE的多项式时间算法0测试是一个统一VPSPACE族（fn（x1，. . . ，xu（n）与一致常数一起，自由多项式代数族（Cn）拥有特殊能力的基金会测试入度u（n）的门，其值在输入（a1，. . .，au（n）），如果fn（a1，.. . ，a u（n））≤ 0，否则为0。注意，可以在以下应用中使用恒定数量的Uniform VPSPACE0系列前面的定义而不是只有一个：通过使用选择变量，将它们全部合并在一个中就足够了。下面的定理3是主要结果 在展示传递定理的过程中在第6.1至6.3节中，我们通过后继引理证明了：我们的方法与[11]相同，但结构上是相反的。定理3. 有一个多项式时间算法，使用Uniform VPSPACE测试，在输入x'上，计算x'的符号条件的秩，其中r∈t为f1，. . . ，fs.6.1截断符号条件截断的符号条件仅仅是{0，1}的元素T。与全符号条件相反，只有两个ases= 0和/= 0是可区分的。 我们用自然的方法定义了一个点x ′的截断符号条件T：Ti=0当且仅当fi（x′）=0.当然，有更少的令人满意的trunated签署条件比完整的，并且当然存在多项式SPA算法来枚举它们。此外，截断的签名条件可以被视为{1，. . .，s}（通过本发明kTTk= 1），因此，使我们能够说的trun ated符号条件的典故。我们x一个顺序 T与典故兼容，并容易计算的par-amount，例如lexiographi秩序。让我们都T（i）的第i个满意的截断签署条件与这个命令.引 理 6. 有 一 个 算 法 使 用 n 中 的 工 作 空 间 多 项 式 ， 其 中 ， 在 输 入（f1，. . . ，fs）和二进制的（i，j），输出第j个T（i）的分量（第i个满意截断符号 条件，条件≤T）。证据对于instan e Cole的并行归并排序算法[8]，使用定理1的算法，然后使用快速并行排序算法就足够了。⊓⊔注意，输入x的截断符号条件是最大截断。条件T满足 i，Ti=1fi（x<$）=0. 所以我们必须找到一个最大值。这将由binary sear h完成。0引理7. 存在多项式的一致VPSPACE族（gn）满足，对于realx和booleani，Y. Σgn（x<$，i）=Σfk（x<$）2.j≤ik/∈ T（j）≤优惠/≤′{−}Spolynomquials.引理7：如果输入x的截断符号条件为√√−′1. 在最小N ′/2−N ′/2和最大N′/ 216 Pas al Koiran and Sylvain Perifel证据引理6断言判定k∈T（j）是否