ECCC-Report TR10-202https://eccc.weizmann.ac.il/report/2010/202Comments and Revisions published for TR10-202en-usFri, 31 Dec 2010 07:06:15 +0200
Paper TR10-202
| Multivariate Polynomial Integration and Derivative Are Polynomial Time Inapproximable unless P=NP |
Bin Fu
https://eccc.weizmann.ac.il/report/2010/202We 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.Fri, 31 Dec 2010 07:06:15 +0200https://eccc.weizmann.ac.il/report/2010/202