Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The P and NP classes relate to decision problems, but what about more calculation centric problems, specifically solving 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?

share|improve this question
    
Relevant: Wikipedia entries for #P and #P-complete. –  user2468 Dec 31 '11 at 0:47

2 Answers 2

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$.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.