HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Complexity of computing the antiderivative of a given function

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thefunctioncomputinggivencomplexityantiderivative

Problem

Disclaimer: I don't know much computational complexity theory. I am nevertheless curious.

If function $f(x)$ has a certain level of computational complexity (which I actually don't know how to measure), what can we then say about the computational complexity of the following indefinite integral?

$$\int f(x) \, \mathrm d x$$

For example, can we say something about how long it takes to approximate the integral of $f$ within an error of $\epsilon$, given that we know how long it takes to compute $f$ within an error of $\epsilon$?

Solution

Kawamura, in his paper Lipschitz Continuous Ordinary Differential Equations
are Polynomial-Space Complete, mentions a classical result of Friedman (Theorem 3.4) which implies that computing the integral of an easy function could be a hard task (check the paper for the exact definitions), essentially since integration is like summing over many different values.

The result mentioned above is in the framework of computable analysis. The answer could be different in other models of computation. See Real-number Computability from the Perspective of Computer Assisted Proofs in Analysis for a recent survey of models of computation on real numbers.

Context

StackExchange Computer Science Q#85890, answer score: 3

Revisions (0)

No revisions yet.