≥≤∈n/Comput.复杂. 13（2004），131-DOI 10.1007/s00037-004-0186-22004年，BürcBirkhause r V erlag，Base l计算复杂度Valiant帕斯卡尔·科瓦兰抽象。设τ（n）是从常数1和2构造整数n ∈ N所需的最小算术运算次数。一个序列xn被称为“易于计算”，如果存在一个多项式p使得对于所有n ≥ 1，τ（xn）≤ p（log n）。 很自然地会猜想，序列如[2nln2]或n！ 不容易计算。在这篇文章中，我们证明了这个猜想的第一个序列的证明将意味着一个超多项式下界的算术电路大小的永久多项式。对于第二个序列，证明将暗示永久或P/ =PSPACE的超多项式下界。关键词Valiant主题分类。68Q15、68Q17、03D15。1. 介绍设τ（n）是从常数1和2构造整数n∈N所需的最小算术运算次数（+、-或×）比如说，τ（22n）=n通过 序列x如果我在tegersissaidtobee“easy to compute” if there exists a polynomial 否则，该序列被称为“难以计算”。如果存在另一个序列，则称该序列N，使得序列anxn易于计算。 是很自然推测出n！最终并不容易计算。Shub和Smale已经证明，如果这个猜想成立，那么在复数域上P = NP（Shub& Smale 1996;Blum et al. 1998）。不幸的是，猜想仍然是开放的，它甚至不知道n！很难计算。 很容易想出其他似乎很难计算的序列的例子为此外，人们很容易猜想，序列[2nln2nn，[2nπn，[2nen，[2n2位数和[（3/2）n]位数都很难计算，但似乎可以省略。De MeloSvaiter（1996）指出，对于每个α>0，几乎所有整数具有性质τ（n）≥（log n）/（log log n）1+ τ。改进的下界τ（n）≥（logn）/log logn，它对几乎所有整数都成立，132柯伊兰CC 13（2004）[详细]∈在莫雷拉成立（1997年）。这些界限让人想起香农我们的结论是，大多数整数都有很高的τ复杂度，但证明特定序列的良好下界似乎相当困难。这种情况再次让人想起计算复杂性理论。在本文中，我们认为，对于某些序列，证明良好的下界τ是困难的，因为它们将导致复杂性理论中主要开放问题的解决（例如永久多项式的电路大小的超多项式下限）。主要结果。四 分之一世纪前，Valiant提出了一个代数版本-P对NP问题（Valiant 1979）他著名的完备性结果的永久意味着类VNP的“容易定义的”家庭的多项式是等于类VP的“容易计算的”家庭当且仅当永久族在VP中，即，可以通过多项式大小的算术电路来计算。在本文中，我们建立Valiant的模型和计算整数的成本之间的关系。基本思想很简单：如果一个整数多项式可以有效地计算，它在整数点的值是低成本的整数。一个困难是，在Valiant的模型中，电路可以使用来自基础字段的任意常数，但我们对“从头开始”计算整数感兴趣。因此，很自然地，我们可以使用Valiant理论的无常数版本。幸运的是，最近Malod（2003）的博士论文（见第2节快速介绍）研究了这样的理论。Valiant模型和计算整数的成本之间的第一个关系例如，在定理3.5中我们证明了存在满足τ（22nln2）的多项式l pp（n）对于所有的n，假设VP0=VNP0（下标0用于表示无常数类）。根据Hamilton循环多项式族HC的完备性，这个假设成立当且仅当HC在VP0中。在第4节中，我们证明了同样的结果在（假定）较弱的假设下也成立。在一个非常不同的方向（代数算法的去随机化），我们注意到，最近在Kabanets Impagliazzo（2004）中研究了这个假设的一些后果，即永久式可以通过多项式大小的算术电路来计算我们在定理5.1中证明，k！如果VP0 = VNP0且P = PSPACE，则最终容易计算这两个等式的结合是一个非常强有力的假设，但目前似乎还无法反驳（在第5节中有更多的讨论）。Valiant133CC 13（2004）[2014 -05 - 23]≥≤≤-×≤≥<$ ∈ {− ×}<$最后，我们在第6节中给出了一个也就是说，我们表明，2 nln 2是很容易计算的，如果永久是在VP0，并与额外的假设，P= PSPACE，我们表明，n！很容易计算。2. 预赛2.1. 整数计算。一个整数n的长度l的计算是一个序列（n-1，n0，n1，. . . ，nl）的整数，使得n−1= 1，n0= 2，n = nl，并且对于每个i2，存在j，k p，则Cr（j，p）= 0。这可以通过对r的归纳来证明，使用以下事实：对于变量的布尔值并且r >1，Cr（j，p）等价于（pr= 1 <$jr= 0）<$（pr= jr<$Cr−1（j1，. . . ，jr-1，p1，. . . ，pr−1））。然后用标准的多项式来表示布尔运算（例如，uv用UV表示，uv用U+V−UV表示）。设Gr（X，J，N，Y，P）=Cr（J，P）Hr（X，J，N，Y）.家庭gr（X，N，P）=Gr（X，J，N，Y，P）j∈{0， 1}ry{0， 1}m（r）在VNP0中，因为Gr在VP0中。通过构造，我们有gr（X，n，p）=通过设置p=p（n），直接遵循公式6.3，r=q（n）（这里我们使用假设p（n）n来确保二进制N的编码适合于R比特）。Q第6.5题。 设（fn）是由（6.2）式定义的多项式族，并另外假定n p（n）是多项式有界函数。如果VP0= VNP0，则（fn）可以由一族大小为（log n）O（1）的无常数电路计算。如果我们只假设永久式在VP0中，则存在多项式有界函数s（n），使得2s（n）fn可以由一族大小为（log n）O（1）的无常数电路计算。P屋顶。如果VP0 = VNP0，则定理6.1的族（gr）在VP0中，并且可以因此，可以通过一族大小为rO（1）的无常数电路来计算。根据公式6.3，我们得到一族无常数电路，其大小为（logn）O（1），其中fn。现在我们只假设永久物在VP0中。根据定理4.3，存在多项式有界函数p，使得族（2p（r）gr）在VP0中，并且结果再次由（6.3）得出。 Q144柯伊兰CC 13（2004）≥∈›→Σ›→[2014 -05-23]k=1k=1k=1第6.6节.设np（n）是多项式有界函数，且p（n）n对所有nN. 设（an）是一个整数序列，对于某个整数b，可以写为p（n）(6.7)an=f（j，n）bj，j=0其中映射（j，n）f（j，n）在] P/poly中。 如果永久家庭在所以，在0的情况下，（an）是很容易计算的。P屋顶。 这是命题4.1的证明的一个变体设（fn）为由公式6.2定义的多项式族如果积式在VP0中，则由Corol- lary 6.5可知，存在一个多项式有界函数s（n）和一族（Cn）大小为（logn）O（1）的无常数回路，它们计算2s（n）fn.以来an=fn （x1，. .. 得双曲余切值.q（n）），其中x为=b2i−1，wehaveτ（2s（n）a）=（logn）O（1）.现在应用引理4.4，其中u=an且v= 2s（n）。Q最后，我们给出了两个结果，分别改进了定理3.5和定理5.1.第6.8章. 如果永久物在VP0中，则序列Ln= 2nln2很容易计算。P屋顶。的这是定理3.5证明的一个变形。 现在我们利用n n2 n−k/k ≤ 2 nln 2 ≤ 1 +因此，An−1≤Ln≤An+n+1，其中An=Ln[2n-k/k。让f（j，n）是指数k∈ {1，. . .，n}，使得权重位2jineradix-2expansionoff[2n-k/k]isequaltoo1. 这是引理3.4的]P函数。因此，我们可以把An写成式（6.7），其中b=2，p（n）=n。从命题6.6可以得出，（An）很容易计算，因此（Ln）也是如此Q第6.9章. 如果永久物在VP0中且P = PSPACE，则n！ 很容易计算。P屋顶。 通过命题6.6，它足以表明，位n！体重可以在对（j，n）的比特大小的空间多项式中计算。这基本上与定理5.1的证明一样。QnValiant145CC 13（2004）D. 贝利， P. BORWEIN S.引用PLOUFFE（1997）.关于快速计算多对数常数 数学Comp. 66，903-913。L. BLUM，F. CUCKER，M. SHUB S. S男（1998年）。复杂性与真实计算斯普林格。P. BurGISSER（2000）. 代数复杂性理论中的完备性与归约。算法计算数学7，斯普林格。Q. CHENG（2003）.论事实的终极复杂性。在Proc. 20th AnnualSymposium onTheoretical Aspects of Computer Science，Lecture Notes in Comput. Sci. 2607，Springer，157W. 德梅洛湾。F. SVAITER（1996）. 计算整数的成本。Proc. Amer. Math.Soc.124，1377卡巴涅茨河我的梦（2004）去随机化多项式恒等式测试意味着证明电路下界。Comput.复杂性13，1-46。R. J.LIPTON（1994年）。直线复杂度和整数分解。第一届数学数论国际研讨会论文集。Sci. 877，斯普林格，71-79。G. MALOD（2003）. 政策和效率。 博士论文，大学 克劳德和伯纳德-里昂1.C. MOREIRA（1997年）。关于算术代价函数的渐近估计。Proc. Amer. Math.Soc.125，347A. SCHOLZ（1937）.第253章.贾雷斯伯德语数学Verein。47，41-42。A. S.HAMIR（1979）。时间复杂度为O（logn）告知。过程Lett. 8，28-31。M. SHUB S. S男（1996年）。关于希尔伯特零点定理的难解性和“P=NP”的代数形式。杜克数学81，47-54.E. G. THURBER（1999）.最小长度加法链的有效生成SIAM J.Comput. 28，1247-1263.L. G. VALIANT（1979）.代数中的完备类。在Proc.11th ACM Sym-20thTheory of Computing，249146柯伊兰CC 13（2004）H. VOLLMER（1999）.电路复杂性介绍：统一方法。文本理论Comput. Sci. EATCS系列，斯普林格。2003年12月10日收到帕斯卡尔·科瓦兰Laboratoirede46岁，69364 Lyon Cedex 07，法国Pascal. ens-lyon.fr
我的内容管理
展开
