Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-202 | 9th December 2010 04:13

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

RSS-Feed




TR10-202
Authors: Bin Fu
Publication: 31st December 2010 07:06
Downloads: 3934
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.



ISSN 1433-8092 | Imprint