On Approximating Univariate NP-Hard Integrals Academic Article uri icon


  • Abstract Approximating I# PART= 1 0∏ nk= 1 cos (xkπt) dt to within an accuracy of 2− n where the input integers {xk} nk= 1 are given in binary radix, is equivalent to counting the number of equal-sum partitions of the integers {xk} and is thus a# P problem. Similarly, integrating this function from zero to infinity and deciding whether the result is either zero or infinity is an NP-Complete problem. Efficient numerical integration methods such as the double exponential formula and the sinc approximation have been around since the mid …

publication date

  • January 1, 2015