# 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

I'm not sure if this is the answer you're looking for, but there is a general algorithm to solve indefinite integrals called the Risch algorithm. Basically, given a set of elementary functions (polynomials, exponentials, logarithms, sin, cos, etc.) one can write the integral of a function composed of elementary functions in a normal form. I'm a little unclear as to when and where decidability comes in (maybe a good starting point is the Wikipedia section on it) but it looks like as a step in the Risch algorithm is deciding the constant problem which is unknown to have an algorithm for it. From the Wikipedia page, it is known that adding the absolute value function makes the problem undecidable (Richardson's Theorem).

If one restricts to definite integrals, then just deciding whether an integral is 0 or not can be NP-Complete as the following integral representation of the Number Partition Problem shows:

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.

-