Multivariate Polynomial Integration and Differentiation Are Polynomial Time Inapproximable Unless P=NP

摘要

We investigate the complexity of approximate integration and differentiation for multivariate polynomials in the standard computation model. For a functor F(·) that maps a multivariate polynomial to a real number, we say that an approximation A(·) is a factor α: N→ N~+ approximation iff for every multivariate polynomial f with A(f) ≥ 0, F(f)/α(n)≤ A(f) ≤ a(n)F(f), and for every multivariate polynomial f with F(f) < 0, α(n)F(f)≤< A{f) ≤F(f)/α(n), where n is the length of f, len(f).For integration over the unit hypercube, [0,1]~d, we represent a multivariate polynomial as a product of sums of quadratic monomials: f{x_1,…, x_d) = ∏_(1≤i≤k)pi{x_1,…,x_d), where pi(x_1,…, x_d) = ∑_(1≤j≤j≤d qi,j(x_j), and each qi,j (x_j) is a single variable polynomial of degree at most two and constant coefficients. We show that unless P = NP there is no a: N→N~+ and A(·) that is a factor a polynomial-time approximation for the integral I_d{f) = ∫[0,1]df(x_1,…,x_d)dx_1...,dxd. For differentiation, we represent a multivariate polynomial as a product quadratics with 0,1 coefficients. We also show that unless P = NP there is no α: N→N~+ and A(·) that is a factor α polynomial-time approximation for the derivative af(x_1,…,x_d)/a_(x_1),…,a_(x_d) at the origin (x_1,…,x_d) = (0,…, 0). We also give some tractable cases of high dimensional integration and differentiation.