Digital Commons Network^™

Intractability Of Integration And Derivative For Multivariate Polynomial And Trigonometric Function, Liang Ding

Theses and Dissertations - UTB/UTPA

We study the hardness of some basic linear operators which involve high dimension integration or derivative. For a multivariate polynomial ��(��1, ⋯ , ����) which has format ∏ ∑ ��1, we show that there is no any factor polynomial time approximation for the integration of ��(��1, ⋯ , ����) in the unit cube [0,1] �� unless P = NP. In addition to polynomials, we extend the discussion to nonlinear function. For a trigonometric function ��(��1, ⋯ , ����) of format ∏ ∑ �������� ∗ , we show that it is #P-hard to compute derivative ����(��) (��1,⋯,����) ����1⋯������ at the origin …