<p>You cannot <em>compute</em> such functions &quot;in P&quot;, or in any conventional complexity class for that matter, for the fundamenal reason that their inputs and outputs are real numbers that cannot be exactly represented in a computer.</p>
<p>You can compute <em>approximations</em> of elementary analytic functions to any given precision on rational inputs in the function class corresponding to uniform <span class="math-container">$\mathrm{TC}^0$</span> (and a fortiori in FP), as long as you take care that the output is not too large: i.e., in the case of <span class="math-container">$\exp$</span>, the inputs are from a bounded domain so that the output cannot get exponentially large.</p>
<p>The same should hold for typical special functions, but this is an open-ended designation so it can't be answered definitively without specifying exactly what functions you mean. Generally speaking, analytic functions given by power series whose coefficients are <span class="math-container">$\mathrm{TC}^0$</span>-computable (which any simple enough &quot;formula&quot; involving polynomials, powers, fractions, factorials, and the like is) can be approximated in <span class="math-container">$\mathrm{TC}^0$</span> on any compact subset of their domain of convergence.</p>

CC BY-SA 4.0
2023-10-11T06:26:14.273Z
2023-10-11T07:00:50.217Z
2023-10-11T07:00:50.217Z
Emil Jeřábek
<p>There exist polynomial - time computable functions, log - space computable functions, and NC - functions. Given this:</p>
<p>To which class do analytic elementary functions, including trigonometric ones, belong?
To which class do analytic special functions belong?
Is the evaluation of their integrals polynomial-time computable, i.e., do they belong to the class P</p>

CC BY-SA 4.0
2023-10-12T12:04:34.240Z
integration of polynomial time computable real functions is PSpace complete.
Kaveh
CC BY-SA 4.0
2023-10-12T12:05:29.707Z
Ker I. Ko's book is a good read on the topic of complexity of real functions.
Kaveh
CC BY-SA 4.0
2023-10-13T00:46:54.437Z
https://www3.cs.stonybrook.edu/~keriko/cca10.pdf
Kaveh
<cc.complexity-theory><complexity-classes><time-complexity><computability>
Complexity of analytic functions and integrals
roignoirewg
# Complexity of analytic functions and integrals

(Asked by: username_0 on 2023-10-10)

There exist polynomial - time computable functions, log - space computable functions, and NC - functions. Given this:

To which class do analytic elementary functions, including trigonometric ones, belong?
To which class do analytic special functions belong?
Is the evaluation of their integrals polynomial-time computable, i.e., do they belong to the class P

**Tags:** cc.complexity-theory, complexity-classes, time-complexity, computability
> **Comments:**
> **username_1**: integration of polynomial time computable real functions is PSpace complete.  
> **username_1**: Ker I. Ko's book is a good read on the topic of complexity of real functions.  
> **username_1**: https://www3.cs.stonybrook.edu/~keriko/cca10.pdf  

---

## 1 answers

### Answer by username_2 on 2023-10-11. Score: 5 | Accepted answer

You cannot *compute* such functions "in P", or in any conventional complexity class for that matter, for the fundamenal reason that their inputs and outputs are real numbers that cannot be exactly represented in a computer.

You can compute *approximations* of elementary analytic functions to any given precision on rational inputs in the function class corresponding to uniform $\mathrm{TC}^0$ (and a fortiori in FP), as long as you take care that the output is not too large: i.e., in the case of $\exp$, the inputs are from a bounded domain so that the output cannot get exponentially large.

The same should hold for typical special functions, but this is an open-ended designation so it can't be answered definitively without specifying exactly what functions you mean. Generally speaking, analytic functions given by power series whose coefficients are $\mathrm{TC}^0$-computable (which any simple enough "formula" involving polynomials, powers, fractions, factorials, and the like is) can be approximated in $\mathrm{TC}^0$ on any compact subset of their domain of convergence.


---

