Multivariate Polynomial Integration and Derivative Are Polynomial Time Inapproximable unless P=NP

Abstract

We investigate the complexity of integration and derivative for multivariate polynomials in the standard computation model. The integration is in the unit cube $[0,1{]}^d$ for a multivariate polynomial, which has format $f(x_1,\cdots ,x_d)=p_1(x_1,\cdots ,x_d)p_2(x_1,\cdots ,x_d)\cdots p_k(x_1,\cdots ,x_d)$, where each $p_i(x_1,\cdots ,x_d)={\sum }_{j=1}^d{q}_j(x_j)$ with all single variable polynomials $q_j(x_j)$ of degree at most two and constant coefficients. We show that there is no any factor polynomial time approximation for the integration ${\int }_{[0,1{]}^d}f(x_1,\cdots ,x_d)d_{x_1}\cdots d_{x_d}$ unless $P=NP$. For the complexity of multivariate derivative, we consider the functions with the format $f(x_1,\cdots ,x_d)=p_1(x_1,\cdots ,x_d)p_2(x_1,\cdots ,x_d)\cdots p_k(x_1,\cdots ,x_d),$ where each $p_i(x_1,\cdots ,x_d)$ is of degree at most $2$ and $0,1$ coefficients. We also show that unless $P=NP$, there is no any factor polynomial time approximation to its derivative $\frac{\partial f^{(d)}(x_1,\cdots ,x_d)}{\partial x_1\cdots \partial x_d}$ at the origin point $(x_1,\cdots ,x_d)=(0,\cdots ,0)$. Our results show that the derivative may not be easier than the integration in high dimension. We also give some tractable cases of high dimension integration and derivative.