# How do you determine the complexity class of a problem like solving an integral?

The P and NP classes relate to decision problems, but what about calculus problems, specifically computing an integral? How does one figure out if a certain class of integrals is in P or NP? Can something like this be rephrased in terms of a decision problem? Or is there another, indirect method?

• Relevant: Wikipedia entries for #P and #P-complete. – user2468 Dec 31 '11 at 0:47

Given $n$ numbers, $(a_0, a_1, \cdots, a_{n-1})$, in the range of $1$ to $M$, find whether the following integral is zero or not: $$\frac{1}{2 \pi} \int_{-\pi}^{\pi}\ \ \prod_{k=0}^{n-1}(e^{i a_k \theta } + e^{ - i a_k \theta }) d\theta$$
Notice that each term in the expanded product will be a combination of all the $a_k$'s. Should one of the combinations in the exponent sum to 0, that term will evaluate to a positive number. Since the $a_k$'s are integers, should the term in the exponent not sum to 0, the integral will evaluate to 0. All terms with a non-zero exponent vanish while all terms with a 0 exponent count for 1 thus providing a "counting" function of all possible solutions.
If one wants to find the actual value of that integral, then this problem becomes $\#P$.
You have to use a higher type model to faithfully talk about complexity and computability of operators in analysis like integration. You may want to check Akitoshi Kawamura's thesis "Computational Complexity in Analysis and Geometry". He proves that integration is $\mathsf{\#P\text{-}complete}$ operator.