5
$\begingroup$

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

Improve this question
$\endgroup$
8
  • $\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
    Commented Dec 25, 2017 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
    Commented Dec 25, 2017 at 9:17
  • $\begingroup$ Is your model of computation RAM? $\endgroup$
    – Complexity
    Commented Dec 25, 2017 at 9:24
  • $\begingroup$ If $f$ polynomial? What error function are you using? $\endgroup$
    – Rodrigo de Azevedo
    Commented Dec 25, 2017 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
    Commented Dec 25, 2017 at 14:43

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you. When you say "computing the integral" does that mean computing the approximation at ever increasing precision? $\endgroup$
    – user56834
    Commented Dec 25, 2017 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
    Commented Dec 25, 2017 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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