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

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 ${\partial f^{(d)}(x_1,\cdots, x_d)\over \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.

No reviews yet.

No comments yet.