Interpolation in Valiant's Theory

被引:12
作者
Koiran, Pascal [1 ]
Perifel, Sylvain [2 ]
机构
[1] Univ Lyon, LIP, Ecole Normale Super Lyon, CNRS,UCBL,INRIA, Lyon, France
[2] Univ Paris Diderot, LIAFA, CNRS, Paris 7, France
关键词
Computational complexity; algebraic complexity; Valiant's model; polynomials; interpolation; Blum-Shub-Smale model; COMPLEXITY;
D O I
10.1007/s00037-011-0002-8
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We investigate the following question: if a polynomial can be evaluated at rational points by a polynomial-time boolean algorithm, does it have a polynomial-size arithmetic circuit? We argue that this question is certainly difficult. Answering it negatively would indeed imply that the constant-free versions of the algebraic complexity classes VP and VNP defined by Valiant are different. Answering this question positively would imply a transfer theorem from boolean to algebraic complexity. Our proof method relies on Lagrange interpolation and on recent results connecting the (boolean) counting hierarchy to algebraic complexity classes. As a by-product, we obtain two additional results: The constant-free, degree-unbounded version of Valiant's hypothesis VP not equal VNP implies the degree-bounded version. This result was previously known to hold for fields of positive characteristic only. If exponential sums of easy to compute polynomials can be computed efficiently, then the same is true of exponential products. We point out an application of this result to the P = NP problem in the Blum-Shub-Smale model of computation over the field of complex numbers.
引用
收藏
页码:1 / 20
页数:20
相关论文
共 21 条
[1]   ON THE COMPLEXITY OF NUMERICAL ANALYSIS [J].
Allender, Eric ;
Buergisser, Peter ;
Kjeldgaard-Pedersen, Johan ;
Miltersen, Peter Bro .
SIAM JOURNAL ON COMPUTING, 2009, 38 (05) :1987-2006
[2]  
[Anonymous], 1997, GRUNDLEHREN MATH WIS
[3]   ON A THEORY OF COMPUTATION AND COMPLEXITY OVER THE REAL NUMBERS - NP-COMPLETENESS, RECURSIVE FUNCTIONS AND UNIVERSAL MACHINES [J].
BLUM, L ;
SHUB, M ;
SMALE, S .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1989, 21 (01) :1-46
[4]  
Blum L., 1998, COMPLEXITY REAL COMP, DOI DOI 10.1007/978-1-4612-0701-6
[5]   ON DEFINING INTEGERS AND PROVING ARITHMETIC CIRCUIT LOWER BOUNDS [J].
Buergisser, Peter .
COMPUTATIONAL COMPLEXITY, 2009, 18 (01) :81-103
[6]   The complexity of factors of multivariate polynomials [J].
Bürgisser, P .
FOUNDATIONS OF COMPUTATIONAL MATHEMATICS, 2004, 4 (04) :369-396
[7]  
Burgisser P., 2000, COMPLETENESS REDUCTI
[8]  
Fournier H, 2000, LECT NOTES COMPUT SC, V1853, P832
[9]  
Fournier H., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P507, DOI 10.1145/276698.276864
[10]   On the complexity of computing determinants [J].
Kaltofen, E ;
Villard, G .
COMPUTATIONAL COMPLEXITY, 2005, 13 (3-4) :91-130