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

  • $\begingroup$ What do you mean by "the computational complexity of a function"? Is it complexity of an algorithm that computes the function $f(x)$? $\endgroup$ – fade2black Dec 25 '17 at 8:00
  • $\begingroup$ @fade2black, yes I think thats what I mean, but since maybe sometkmes the integral cannot be computed (i dont know if thats true) lets say we require it to be computed within error $\epsilon$ $\endgroup$ – user56834 Dec 25 '17 at 9:17
  • $\begingroup$ Is your model of computation RAM? $\endgroup$ – Complexity Dec 25 '17 at 9:24
  • $\begingroup$ If $f$ polynomial? What error function are you using? $\endgroup$ – Rodrigo de Azevedo Dec 25 '17 at 9:50
  • 1
    $\begingroup$ @YuvalFilmus, Why are you forcing me, a complete amateur, to choose a model of computation? My decision can only be random or ill informed. Doesn't it make a lot more sense for someone like yourself to choose the model based on what makes sense? I don't even know exactly what it means to choose a model of computation. I am just wondering whether, roughly, "all integrals of tractable functions are tractable". $\endgroup$ – user56834 Dec 25 '17 at 14:43

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.

  • $\begingroup$ Thank you. When you say "computing the integral" does that mean computing the approximation at ever increasing precision? $\endgroup$ – user56834 Dec 25 '17 at 15:50
  • $\begingroup$ You'll have to check the paper for the exact definitions, but generally speaking, in computable analysis, a "real number" is a machine that accepts a tolerance $\epsilon$ and returns a rational $\epsilon$-approximation to the number. For the definition of "real function" you'll have to check the paper. $\endgroup$ – Yuval Filmus Dec 25 '17 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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