1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ integration of polynomial time computable real functions is PSpace complete. $\endgroup$
    – Kaveh
    Commented Oct 12, 2023 at 12:04
  • $\begingroup$ Ker I. Ko's book is a good read on the topic of complexity of real functions. $\endgroup$
    – Kaveh
    Commented Oct 12, 2023 at 12:05
  • $\begingroup$ www3.cs.stonybrook.edu/~keriko/cca10.pdf $\endgroup$
    – Kaveh
    Commented Oct 13, 2023 at 0:46

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

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.