实数上的稀疏性与图灵约化

7网址：http://www.elsevier.nl/locate/entcs/volume67.html8页实数上的稀疏性与图灵约化Felipe Cu cker1;2部门数学中华人民共和国香港城市大学摘要本文证明了实数域上不同设置下的NP-完全和NP-难（图灵约化）稀疏集关键词：实计算，图灵约简，稀疏性1引言近年来发表了一些论文处理扩展Mahaney定理计算的实数。Mahaney定理[13]指出，除非P = NP，否则不存在稀疏NP-硬集。AsetSf0;1g 当存在一个多项式p，使得对于所有n2IN，子集SnS中所有具有大小n的元素的基数最多为p（n）。这里f0;1g 表示f0;1 g中元素n t的所有nite序列的集合。Mahaney定理回答了一个起源于Berman-Hartmanis猜想的问题. 后者指出，所有的NP-完备集（f0;1 g）是p多项式同构的。也就是说，对所有的NP-完备集A和B，存在一个双射'：f0;1g ！f0;1g suchx2A当且仅当'（x）2B. 此外，both'和它的逆可以在多项式时间内计算。Berman-Hartmanis猜想尚未被证明。如果它被证明，我们将得到的结果是不存在稀疏NP完全集。如果我们假设P6 = NP，这是马哈尼定理所暗示的1982年以后，围绕着约简到“小”集合的问题展开了一系列研究（见[1]）。1 部分由SRG赠款7001290支持。2 电子邮件地址：macucker@math.cityu.edu.hk2002年由ElsevierScienceB. V. 操作访问根据C CB Y-NC-N D许可证进行。8nMahaney定理推广到实数机器[4]中所介绍的，也见[3]）是在[7]中首次提出的。第一个问题是如何将稀疏性的概念推广到IR1的子集（I R N的分离 对于n2IN）。 在[7]中提出的概念是以下翼。 让S1R1. 我们说S是稀疏的，如果对于所有n1，S=fx2Sjx2IRng对于某个固定的q，维数至多为logqn。 这里维数是Sn的Zebrski闭包在代数几何意义下的维数。使用稀疏性的概念，[7]的主要结果证明了在（IR; +;=）上的机器的上下文中不存在稀疏NP-硬集，即，不执行乘法或除法，只在相等测试时进行分支的机器。 注意，这个结果不以不等式P 6= NP为条件，因为这个不等式在这个设置中是真的（参见图1）。[14]）。此外，我们还想指出，在上述结果中考虑NP-难性所隐含的归约概念是所谓的“多一”。“对[7]中结果的自然扩展将考虑（IR;+;）上的机器。也就是说，机器不执行乘法或除法，但允许在不等式测试上分支。虽然没有证据表明不存在稀疏NP-困难集（关于多1约简，假设P NP）在这种情况下，Fournier和Koiran [11]的结果表明，存在关于图灵约简的NP完全稀疏集。这是由一个令人惊讶的结果（[11]中的引理3）得出的，粗略地说，该结果表明，对于图灵约化，f 0; 1g上的任何NP完全集都是（IR;+;）上的NP完全集由于任何这样的集合S的大小为n的元素的子集的维数为0，S的稀疏性是直接的。一个自然的问题出现了。（IR; +;=）上的图灵约简是否存在稀疏NP-困难集？Fournier在[10]中给出了部分答案，证明了（IR;+;=）上不存在关于图灵约简的稀疏可定NP-难集。由于NP中的任何集合都是可定义的，一个直接的结果（奇怪的是在[10]中没有提到）如下。命题1.1在（IR;+;=）上不存在稀疏NP-图灵完备集。可确定性条件很重要。证明以下内容非常容易（见下文第2节）。命题1.2（IR;+;=）上存在稀疏的NP-图灵-硬集。Koiran在[12]中引入了一个真实机器的模型，允许乘法和除法，试图接近图灵机（在某种意义上，迭代乘法在某种程度上是不利的） Koiran称之为weak的这个模型， 但不再将计算成本度量为所执行的算术运算的数量 被机器。相反，每个单独操作的成本xy取决于9添加添加从输入数据和机器常数中得出x和y项的操作序列。对于该模型，还已知，P 6= NP [8]。在[6]中，证明了不存在稀疏NPW-硬集（关于多-一约简）。这里NPW表示弱模型的类NP。本文的第二个结果将Fournier的结果推广到弱语境。它实际上比Fournier的结果更强，因为我们不需要假设可确定性;相反，它适用于满足许多条件的任何集合族。定义1.3设F是一个集合族，使得每个S2F都包含在IRn中，对于某个n1。我们说F是行为良好的，当(i) F包含半代数集。(ii) F在nite并、交和补下是闭的。(iii) F在欧氏拓扑的内部和闭包下是闭的。(iv) 如果U2F， UIRn和'：U！ IRm是有理映射，则对所有的S2F，SIRm，'1（S）2F和对所有的S2F，SU'（S）2F.(v) 维数的概念是定义良好的，它与通常的半代数集相一致。特别是，F中没有一个集合可以包含一个比它自己的维度更大的集合，或者可以写为一个更小维度集合的集合的集合并。设S2F或S1R1为 因此，对于所有n，S\IRn2F都是良好行为。行为良好的集合族确实存在。最明显的例子是半代数集合族。但是上面的定义涵盖了更一般的集合族。一个主要的注释是o-极小结构是行为良好的族（关于o-极小结构及其几何的概述，请参见[5]或[15]）。因此，特别地，全局次分析集族[9]或通过Pfaustan函数定义的集族[16]是行为良好的。让我们用NPW表示弱模型的NP问题类命题1.4不存在稀疏的行为良好的NP W-图灵-硬集。特别地，不存在稀疏NP W-图灵完备集。2命题1.2和1.4我们记为byNP=和NP<（IR; +;=）上NP问题的类和（IR;+; ）分别。第1.2条建议。设Sf0;1g 是一个（经典的）NP完全集，并考虑S =f（1; x）j x2Sg [f（2; y）j y2IR; y0g：10添加添加添加Wn显然S 是稀疏的，作为IR1的子集。我们现在知道它是NP=- 图灵难.要做到这一点，考虑任何集合A2NP=.显然，A2 NP<也 但然后，Fournier和Koiran [11]证明了存在一个在（IR;+;）上的预言机M在多项式时间内用预言机S解A我们修改M如下。我们将测试z值是否为正的分支节点替换为测试（2; z）2S的oracle节点。我们用测试（1; x）2的oracle节点来代替测试向量x是否为2的S. 很明显，新机器是一个在（IR; +;=）上的oracle机器，oracleS在多项式时间内决定A。下面我们来证明命题1.4。设C=fx2IRnjx2n ++x2n =lg和CIR1e是n1n集合Cn. 我们知道C2NPW.建议2.1LetF是一个具有良好生物学特性的家族，而S1R1 使得S\IRn2Ffor all n. 假设S是NP- 图灵-硬集。 然后，对于所有n 1，存在集合E; 2F，E IRn和C，一个数m 2 IN，m=nO（1），和一个关系映射h：IRn！IRm，我们在E和E\上定义，使得（i）E=;(ii) dim（E\）= n1，(iii) h的分量的分子和分母的次数由n中的多项式限定，并且（iv）h（ E\）\ h（ E）= ;.证据由于C2NPW，存在一个预言机M，它与预言机S一起在弱多项式时间内决定C设p是M的多项式时间界。考虑n2 IN。在大小为n的输入上的M的计算导致深度至多为p（n）的计算树，其分支节点是sign test或oracle节点。设为树中的一个分支节点。如果是符号测试，则测试“（x）0where”是否是有理函数，x 2 IR n是否是输入。此外，由于p是M的弱运行时间的界，所以“的相对素表示的分子和分母都 有 p（n）的度界。如果相反是一个oracle节点，则它测试'（x）=（'1（x）; ：;'m（x））2Sm其中m p（n），并且对于i= 1;：; m，i是如上的有理函数。注意，由于F在有理映射的补像和逆像下是闭的，因此集合f x 2 IR n j '（x）2 Sm g和f x 2 IR n j'（x）62 Smg在F中。如果是一个符号测试，则类似的评论也成立。110n1`nmi对于树中的任何叶子，我们用IRn中计算结束的点的集合表示。这是F中的一个集合，因为它是F中集合的交集。现在设A为接受叶的集合。然后，Cn=[：2A由于dim（Cn）= n 1，并且上面的并集是F中集合的有限并集，所以存在一个叶子2 A，使得dim0= n 1.因此，0是Cn的子集，它属于F，并且它具有最大维数（在2 A中）。让成为通向0的情况。 领域 是=fx2IRn j x到达节点g及其排除部分，E=fx 2 jx偏离从通向0g的路径：如果;：;是通向0的路径中的分支节点，然后我们有1`不相交的联合IR0 =E 1[[E `：再一次，我们注意到E1;：; E `都是F中的集合。我们接下来证明存在i使得dim（E i\0）= n1。这是因为，由于采取关闭通勤与尼特工会，因此，我们认为，IR n =E[[E：0=（0\E 1）[[（0\E `）并且，由于dim0=n 1，因此存在i `使得dim（0\E i）= n1。设E = Ei，i = 0，且h =i，h： ！IR. 我们刚刚证明了dim（\E）= n1，因此，（ii）保持。 此外，0（ i）（第（iii）部分如下，正如我们已经说过的，从M的弱点。 最后，对于第（四）部分，考虑rst如果我是一个Oraclen o de。则对于S，或者Smi 或它的补语，we11c c有E i ='i（S）且0i（S），其中表示互补，并且因此h（E\）\h（E）=;。类似的推理成立，如果i是测试节点其中S现在是IR+或IR f0g。将使用以下实代数几何结果。 它的证明可以在[3]的第19章中找到命题2.2Letf2IR[x1; ： ：;xn]是一个不可约多项式，使得其零点集Z（f）IRn的维数为n1.然后，对于任何多项式g2IR[x1; ： ：;xn]，g在Z（f）上为零当且仅当g是f的倍数。12nKKKBn命题2.3利用命题2.1的符号，令k1 = dim h（E\）的。(i) 存在指数i1; ： ;ik2f1; ：;mg，一个多项式g2IR[y1; ： ：;yk]和一个有理数函数q2IR（x1; ：;xn），其中b为有理数，且分母与fn互素，使得g（hi1; ：;hi）=f`q对于一些“0。(ii) 对于n足够大，kn.是的。 设K=dimh（E）. 由于dimh（E）=K，存在i1; ：;iK2f1; ：;mgsuch，函数hi1; ：;hi是代数上不可分的。接下来我们要证明K。为此，令X= h（E\ dom（h））;Y =h（E）和Z=h（E1）。这里，do m（h）表示IRn中的点的集合，其中h是任意的。 我们证明了所有的X、Y和Z都是F在IRm中的集合。此外，Z包含在Y关于相对于X的欧几里德拓扑的闭包中，因为h是连续的，并且Y\Z =;由命题2.1（iv）。从这里可以得出，Z包含在Y相对于X的边界中。因此，dim Z dim Y = dim X。以上表明，dim h（E1）