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

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

2010-12-10

arxiv.org/abs/1012.2377v1

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Multivariate Polynomial Integration and Derivative Are Polynomial Time Inapproximable unless P=NP does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Multivariate Polynomial Integration and Derivative Are Polynomial Time Inapproximable unless P=NP, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multivariate Polynomial Integration and Derivative Are Polynomial Time Inapproximable unless P=NP will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-105096