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

$\alpha\colon N \to N^+$

approximation

iff for every multivariate polynomial

f

with

A

(

f

) ≥ 0,

$\frac{F(f)}{\alpha(n)} \le A(f) \le \alpha(n)F(f)$

, and for every multivariate polynomial

f

with

F

(

f

) < 0,

$\alpha(n) F(f) \le A(f) \le \frac{F(f)}{\alpha(n)}$

, where

n

is the length of

f

,

$\textit{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

p

i

(

x

1

,…,

x

d

), where

p

i

(

x

1

,…,

x

d

) = ∑ 

1 ≤ 

j

 ≤ 

d

q

i

,

j

(

x

j

), and each

q

i

,

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

$\alpha\colon N\to N^+$

and

A

(·) that is a factor

α

polynomial-time approximation for the integral

$I_d(f) = \int_{[0,1]^d} f(x_1,\ldots , x_d)d\,x_1,\ldots,d\,x_d$

.

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

$\alpha\colon N\to N^+$

and

A

(·) that is a factor

α

polynomial-time approximation for the derivative

$\frac{\partial f(x_1,\ldots , x_d)}{\partial x_1,\ldots,\partial x_d}$

at the origin (

x

1

, …,

x

d

) = (0, …, 0). We also give some tractable cases of high dimensional integration and differentiation.