We define problem $A$ as follows. Each instance of the problem consists of:

(a) some succinct codification of an elementary function, that is, a function constructed by composing arithmetic operators, $exp$, $log$, $sin$, $cos$, and their inverses (e.g. $\frac{log(sin^{-1}(x))}{2} * cos(3x)$). The codification denotes in some way the syntactic structure of the expression defining the function (e.g. a tree where operation $*$ is performed at the root, the left subtree denotes $\frac{log(sin^{-1}(x))}{2}$, the right subtree denotes $cos(3x)$, and so on);

(b) some rational number $x\in \mathbb{Q}$; and

(c) some natural number $n\in \mathbb{N}$,

and we want to compute $n$ digits of the provided elementary function at input $x$.

I read here that it not known whether $O(M(n)\log n)$ is the optimal complexity for elementary functions, where $M(n)$ is the complexity of multiplying $n$-digit numbers. I have the following questions:

(1) The table shown in that source also says that some $O(M(n)\log n)$ algorithms are known whose applicability covers the basic functions "$exp$, $log$, $sin$, $cos$, $arctan$." Does this bound apply as well to any elementary function (where these operators, as well as the arithmetic ones, can be freely composed in any way)?

(2) Assuming there is some proof that any elementary function can be computed in time $O(M(n)\log n)$, I guess this statement would apply to each specific elementary function $f$. That is, we have a different problem $P_f$ for each elementary function $f$, and each problem $P_f$ can be solved in $O(M(n)\log n)$ time. This would not imply by itself that problem $A$ can be solved in polynomial time. For instance, maybe the length of each $O(M(n)\log n)$-time program computing each problem $P_f$ is exponential with respect to the size of the syntactic tree denoting function $f$ (e.g. maybe dealing with some very long built-in function expansion is required for each $f$). Can problem $A$ be solved in polynomial time?

  • 2
    $\begingroup$ The question sweeps so many things under the rug in so many naive ways that it hardly makes any sense as stated. In random order: (1) It’s a very, very bad idea to ask the function to compute $n$ digits of its expansion. Apart from polynomials (that map exact rational values to exact rational values), no algorithms for elementary functions naturally compute the digits. They only compute an approximation of the value up to a stated precision (and there is no way of telling whether it is an overapproximation or underapproximation). For the most simple elementary functions, you can then ... $\endgroup$ Jan 10 at 9:31
  • 3
    $\begingroup$ ... compute a given number of digits by employing results from diophantine approximation (e.g., the finite irrationality measure of $\pi$) that give an upper bound on the required precision of approximation. But already for the composition of two such functions, there are usually no such results known. In their absence, not only there is no complexity bound on the running time of computing the digits, but if you do not know whether the result may be an exact rational by coincidence, the digits may not be computable at all. If you are getting better and better approximations of the form ... $\endgroup$ Jan 10 at 9:37
  • 3
    $\begingroup$ ... $0{.}1635999999999999\dots$, you cannot know whether the true value to four digits of precision is $0{.}1635$ or $0{.}1636$. And even in cases where you do have the required diophantine results, they only apply if the argument is an exact rational; but once you are computing the composition $f(g(x))$, the argument to $f(x)$ will not be edact, but itself only an approximation, hence the results will not apply. (2) You cannot compute an $n$-digit approximation of $\exp(x)$ in time $O(M(n)\log n)$. There is no way around the fact that $\exp$ grows exponentially; even if you are using a .... $\endgroup$ Jan 10 at 9:42
  • 2
    $\begingroup$ ... floating point representation with mantissa and exponent, the exponent of the result will be exponentially longer than the exponent of the input, and will require exponential time to output, let alone compute. This gets worse when iterating the functions, such as $f(\exp(x))$. The $O(M(n)\log n)$ bounds only hold if you are computing approximations of the stated functions on a fixed compact domain included in a region where the function is analytic (i.e., not touching any singularities, branching points, and the like). This will, in particular, make the result of the function bounded ... $\endgroup$ Jan 10 at 9:47
  • 3
    $\begingroup$ ... by a constant. (3) Richardson’s theorem ensures that it is undecidable whether the result of evaluation of an elementary function is exactly $0$. Even though you are only computing approximations, this may make the problem undecidable in various way. First, it is undecidable to compute exact digits (cf. point (1)). Second, it may be undecidable to determine whether all the intermediate arguments in a composition like $f(g(h(x)))$ are in the domains of the respective functions. Third, depending on how exactly you define it, ... $\endgroup$ Jan 10 at 9:55


Your Answer

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