__
TR10-202 | 9th December 2010 04:13
__

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

TR10-202
Authors:

Bin Fu
Publication: 31st December 2010 07:06

Downloads: 3714

Keywords:

**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

${\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 $\#P$-hard result for derivative shows that the

derivative is not be easier than the integration in high

dimension. We also give some

tractable cases of high dimension integration and derivative.