<p>We define problem <span class="math-container">$A$</span> as follows. Each instance of the problem consists of:</p>
<p>(a) some succinct codification of an <a href="https://en.wikipedia.org/wiki/Elementary_function" rel="nofollow noreferrer">elementary function</a>, that is, a function constructed by composing arithmetic operators, <span class="math-container">$exp$</span>, <span class="math-container">$log$</span>, <span class="math-container">$sin$</span>, <span class="math-container">$cos$</span>, and their inverses (e.g. <span class="math-container">$\frac{log(sin^{-1}(x))}{2} * cos(3x)$</span>). The codification denotes in some way the syntactic structure of the expression defining the function (e.g. a tree where operation <span class="math-container">$*$</span> is performed at the root, the left subtree denotes <span class="math-container">$\frac{log(sin^{-1}(x))}{2}$</span>, the right subtree denotes <span class="math-container">$cos(3x)$</span>, and so on);</p>
<p>(b) some rational number <span class="math-container">$x\in \mathbb{Q}$</span>; and</p>
<p>(c) some natural number <span class="math-container">$n\in \mathbb{N}$</span>,</p>
<p>and we want to compute <span class="math-container">$n$</span> digits of the provided elementary function at input <span class="math-container">$x$</span>.</p>
<p>I read <a href="https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Elementary_functions" rel="nofollow noreferrer">here</a> that it not known whether <span class="math-container">$O(M(n)\log n)$</span> is the optimal complexity for elementary functions, where <span class="math-container">$M(n)$</span> is the complexity of multiplying <span class="math-container">$n$</span>-digit numbers. I have the following questions:</p>
<p>(1) The table shown in that source also says that some <span class="math-container">$O(M(n)\log n)$</span> algorithms are known whose applicability covers the basic functions &quot;<span class="math-container">$exp$</span>, <span class="math-container">$log$</span>, <span class="math-container">$sin$</span>, <span class="math-container">$cos$</span>, <span class="math-container">$arctan$</span>.&quot; Does this bound apply as well to <em>any</em> elementary function (where these operators, as well as the arithmetic ones, can be freely composed in any way)?</p>
<p>(2) Assuming there is some proof that <em>any</em> elementary function can be computed in time <span class="math-container">$O(M(n)\log n)$</span>, I guess this statement would apply to each <em>specific</em> elementary function <span class="math-container">$f$</span>. That is, we have a different problem <span class="math-container">$P_f$</span> for each elementary function <span class="math-container">$f$</span>, and each problem <span class="math-container">$P_f$</span> can be solved in <span class="math-container">$O(M(n)\log n)$</span> time. This would <em>not</em> imply by itself that problem <span class="math-container">$A$</span> can be solved in polynomial time. For instance, maybe the length of each <span class="math-container">$O(M(n)\log n)$</span>-time program computing each problem <span class="math-container">$P_f$</span> is exponential with respect to the size of the syntactic tree denoting function <span class="math-container">$f$</span> (e.g. maybe dealing with some very long built-in function expansion is required for each <span class="math-container">$f$</span>). Can problem <span class="math-container">$A$</span> be solved in polynomial time?</p>

CC BY-SA 4.0
2024-01-09T15:47:05.860Z
Just out of curiosity.... Do you want to compute $n$ digits from most significant to least significant OR from least significant to most significant?
Tayfun Pay
CC BY-SA 4.0
2024-01-09T16:05:17.850Z
From most significant to least significant. I want to get the best approximation to the actual value, so if the actual value is e.g. 12345 and n=3, knowing that the answer is 123xx is more interesting than knowing that the answer is xx345...
EXPTIME-complete
CC BY-SA 4.0
2024-01-10T09:31:37.327Z
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 ...
Emil Jeřábek
CC BY-SA 4.0
2024-01-10T09:37:28.967Z
... 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 ...
Emil Jeřábek
CC BY-SA 4.0
2024-01-10T09:42:26.207Z
... $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 ....
Emil Jeřábek
CC BY-SA 4.0
2024-01-10T09:47:13.117Z
... 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 ...
Emil Jeřábek
CC BY-SA 4.0
2024-01-10T09:55:41.307Z
... by a constant. (3) [Richardson’s theorem](https://en.wikipedia.org/wiki/Richardson%27s_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, ...
Emil Jeřábek
CC BY-SA 4.0
2024-01-10T10:02:19.907Z
... even an “approximation” may determine exact equality with $0$ after all. There are two basic types of approximation: additive approximation, where if the result is $z$ and the desired precision is $n$ bits, you compute a $z'$ s.t. $z-2^{-n}\le z'\le z+2^{-n}$, and multiplicative approximation, where you compute $z'$ s.t. $(1-2^{-n})z\le z'\le(1+2^{-n})z$ (or vice versa, if negative). Computing $n$ most significant digits (up to an ambiguity in the last digit, see point (1)), which your wording of the question suggests, corresponds to *multiplicative* approximation, and multiplicative ...
Emil Jeřábek
CC BY-SA 4.0
2024-01-10T10:07:45.247Z
... approximation preserves exact equality to $0$, as well as the sign of the result. Thus, it is again undecidable by Richardson’s theorem. Additive approximation is better behaved in this respect, but if you are composing functions where the intermediate results are given by additive approximation, it effectively means the functions must be uniformly continuous with a nicely computable mudulus of uniform continuity. This, again, reinforces the point that you may only consider each basic elementary function $f$ to be defined on a fixed compact subset of its domain of analyticity.
Emil Jeřábek
CC BY-SA 4.0
2024-01-10T10:16:26.973Z
Note that Richardson’s theorem needs $|x|$, which you didn’t explicitly list in the question, but if you are not careful, this function will be definable through other means (e.g., as $\sqrt{x^2}$ or $\exp(\frac12\log(x^2))$). Even if you take precautions ensuring that $|x|$ is not definable by a composition of basic functions, the theorem should warn you that the problem *may* be even noncomputable without a compelling reason otherwise. So asking about its computational complexity is premature.
Emil Jeřábek
CC BY-SA 4.0
2024-01-10T16:13:26.990Z
Thank you very much for your explanation, Emil. I see I was misled by the sentence *"It is not known whether $O(M(n)\log n)$ is the optimal complexity for elementary functions"* in that Wikipedia entry, as I assumed it implied it is known that we can compute all of these functions (including those created by composition of several basic functions) in time $O(M(n)\log n)$ ---although it is not known whether we can do better. In fact, no conditions for this complexity result are mentioned there (e.g. there is no mention to ...
EXPTIME-complete
CC BY-SA 4.0
2024-01-10T16:14:58.070Z
... assuming a fixed compact domain included in a region where the function is analytic, as you say), so I guess the presentation there is somehow misleading. I wrote my question in terms of that known result in particular because I thought it would be easier getting an answer to the question I'm actually interested in, which is a weaker condition: given (a) any elementary funtion $f$ (actually, $exp$ and $log$ can be removed from the repertory of basic functions because I don't need them, but I do need to use composition); and (b) an $x$ such that *it is assumed $f(x)=1$ or $f(x)=3$*, ...
EXPTIME-complete
CC BY-SA 4.0
2024-01-10T16:17:01.020Z
... find out which one is true. Hence, I don't need $n$ digits, I just need some (coarse!) approximation to $f(x)$, just a separation between two possible natural values. What is the complexity of making this decision? The function $f$ could or could not include singularities (I'm trying to constrain the problem to functions without them, but I don't know if it will be possible). If the answer to the question I posted had been yes (i.e. if problem A were polynomial), then the problem I'm actually interested in (say problem B) would be polynomial as well. ...
EXPTIME-complete
CC BY-SA 4.0
2024-01-10T16:17:57.543Z
... But problem A (without any further constraints) is not decidable in general, as you say. Is problem B polynomial (or at least decidable)?
EXPTIME-complete
CC BY-SA 4.0
2024-01-11T07:21:40.087Z
@EmilJeřábek, I suggest putting all of that in an answer.  It reads like an answer to me.  "Frame challenges" can be valid answers.
D.W.
CC BY-SA 4.0
2024-01-11T10:48:50.007Z
Yes, the answer by @EmilJeřábek is a great answer to my question as it is stated. Still, I would be thankful if any hint about the alternative problem B mentioned in my previous comments can be solved in polynomial time. Can we separate in polynomial time the cases $f(x) = a$ and $f(x) = b$, where $a$ and $b$ are any given two different natural numbers, assuming $f$ is any elementary function composed without using $exp$ and $log$? (If the answer is not simple, then I could state it in a new post.)
EXPTIME-complete
CC BY-SA 4.0
2024-01-11T13:20:30.387Z
If you want to evaluate arbitrary expressions, you can’t expect this to be doable in polynomial time, even for a very simple list of basic functions. Even a moderately increasing function can exponentially blow up when iterated. This is the reason why, e.g., Polynomial Identity Testing is not known to be computable in (deterministic) polynomial time. I’m pretty sure no subexponential algorithm is known to compute approximations of $\cos((\cdots((x\underbrace{{}^2)^2)^2\cdots)^2}_n)$. You might object that if the input expression is supposed to be given as a tree, and we have only binary ...
Emil Jeřábek
CC BY-SA 4.0
2024-01-11T13:26:03.230Z
... $x\cdot y$ as a primitive operation rather than $x^2$, then this expression takes size $O(2^n)$ to write down; but you can use other unary functions with similar properties: e.g., $\cos(1/(\underbrace{1-\cos(1-\cos(1-\cos(\cdots(1-\cos{}}_nx)\cdots)))))$ (the point is that for small $x$, $1-\cos x\approx x^2/2$). I’m pretty sure no subexponential time algorithm is known to approximate such a function, or even to distinguish whether the value is $0$ or $1$ (though, I guess, Schanuel’s conjecture or the like might imply that the result cannot be rational at all on exact rational input).
Emil Jeřábek
CC BY-SA 4.0
2024-01-11T22:15:27.370Z
Ok, I see! So for the function you propose, separating outputs 0 and 1 would require an exponential precision or an exponential number of digits, which means requiring exponential time if we are using Taylor expansion in particular. Although it seems it is not known yet whether this problem is NP-hard (or worse), state-of-the-art algorithms cannot cope with this problem in polynomial time. Thank you very much, your comments clarified a lot and are a great answer!
EXPTIME-complete
<time-complexity><na.numerical-analysis>
Complexity of, given any elementary function $f$ and a natural $n$, compute $n$ digits of $f(x)$
EXPTIME-complete
# Complexity of, given any elementary function $f$ and a natural $n$, compute $n$ digits of $f(x)$

(Asked by: username_0 on 2024-01-09)

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

(a) some succinct codification of an [elementary function](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Elementary_functions) 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?

**Tags:** time-complexity, na.numerical-analysis

> **Comments:**
> **username_1**: Just out of curiosity.... Do you want to compute $n$ digits from most significant to least significant OR from least significant to most significant?  
> **username_0**: From most significant to least significant. I want to get the best approximation to the actual value, so if the actual value is e.g. 12345 and n=3, knowing that the answer is 123xx is more interesting than knowing that the answer is xx345...  
> **username_2**: 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 ...  
> **username_2**: ... 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 ...  
> **username_2**: ... $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 ....  
> **username_2**: ... 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 ...  
> **username_2**: ... by a constant. (3) [Richardson’s theorem](https://en.wikipedia.org/wiki/Richardson%27s_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, ...  
> **username_2**: ... even an “approximation” may determine exact equality with $0$ after all. There are two basic types of approximation: additive approximation, where if the result is $z$ and the desired precision is $n$ bits, you compute a $z'$ s.t. $z-2^{-n}\le z'\le z+2^{-n}$, and multiplicative approximation, where you compute $z'$ s.t. $(1-2^{-n})z\le z'\le(1+2^{-n})z$ (or vice versa, if negative). Computing $n$ most significant digits (up to an ambiguity in the last digit, see point (1)), which your wording of the question suggests, corresponds to *multiplicative* approximation, and multiplicative ...  
> **username_2**: ... approximation preserves exact equality to $0$, as well as the sign of the result. Thus, it is again undecidable by Richardson’s theorem. Additive approximation is better behaved in this respect, but if you are composing functions where the intermediate results are given by additive approximation, it effectively means the functions must be uniformly continuous with a nicely computable mudulus of uniform continuity. This, again, reinforces the point that you may only consider each basic elementary function $f$ to be defined on a fixed compact subset of its domain of analyticity.  
> **username_2**: Note that Richardson’s theorem needs $|x|$, which you didn’t explicitly list in the question, but if you are not careful, this function will be definable through other means (e.g., as $\sqrt{x^2}$ or $\exp(\frac12\log(x^2))$). Even if you take precautions ensuring that $|x|$ is not definable by a composition of basic functions, the theorem should warn you that the problem *may* be even noncomputable without a compelling reason otherwise. So asking about its computational complexity is premature.  
> **username_0**: Thank you very much for your explanation, Emil. I see I was misled by the sentence *"It is not known whether $O(M(n)\log n)$ is the optimal complexity for elementary functions"* in that Wikipedia entry, as I assumed it implied it is known that we can compute all of these functions (including those created by composition of several basic functions) in time $O(M(n)\log n)$ ---although it is not known whether we can do better. In fact, no conditions for this complexity result are mentioned there (e.g. there is no mention to ...  
> **username_0**: ... assuming a fixed compact domain included in a region where the function is analytic, as you say), so I guess the presentation there is somehow misleading. I wrote my question in terms of that known result in particular because I thought it would be easier getting an answer to the question I'm actually interested in, which is a weaker condition: given (a) any elementary funtion $f$ (actually, $exp$ and $log$ can be removed from the repertory of basic functions because I don't need them, but I do need to use composition); and (b) an $x$ such that *it is assumed $f(x)=1$ or $f(x)=3$*, ...  
> **username_0**: ... find out which one is true. Hence, I don't need $n$ digits, I just need some (coarse!) approximation to $f(x)$, just a separation between two possible natural values. What is the complexity of making this decision? The function $f$ could or could not include singularities (I'm trying to constrain the problem to functions without them, but I don't know if it will be possible). If the answer to the question I posted had been yes (i.e. if problem A were polynomial), then the problem I'm actually interested in (say problem B) would be polynomial as well. ...  
> **username_0**: ... But problem A (without any further constraints) is not decidable in general, as you say. Is problem B polynomial (or at least decidable)?  
> **username_3**: @EmilJeřábek, I suggest putting all of that in an answer.  It reads like an answer to me.  "Frame challenges" can be valid answers.  
> **username_0**: Yes, the answer by @EmilJeřábek is a great answer to my question as it is stated. Still, I would be thankful if any hint about the alternative problem B mentioned in my previous comments can be solved in polynomial time. Can we separate in polynomial time the cases $f(x) = a$ and $f(x) = b$, where $a$ and $b$ are any given two different natural numbers, assuming $f$ is any elementary function composed without using $exp$ and $log$? (If the answer is not simple, then I could state it in a new post.)  
> **username_2**: If you want to evaluate arbitrary expressions, you can’t expect this to be doable in polynomial time, even for a very simple list of basic functions. Even a moderately increasing function can exponentially blow up when iterated. This is the reason why, e.g., Polynomial Identity Testing is not known to be computable in (deterministic) polynomial time. I’m pretty sure no subexponential algorithm is known to compute approximations of $\cos((\cdots((x\underbrace{{}^2)^2)^2\cdots)^2}_n)$. You might object that if the input expression is supposed to be given as a tree, and we have only binary ...  
> **username_2**: ... $x\cdot y$ as a primitive operation rather than $x^2$, then this expression takes size $O(2^n)$ to write down; but you can use other unary functions with similar properties: e.g., $\cos(1/(\underbrace{1-\cos(1-\cos(1-\cos(\cdots(1-\cos{}}_nx)\cdots)))))$ (the point is that for small $x$, $1-\cos x\approx x^2/2$). I’m pretty sure no subexponential time algorithm is known to approximate such a function, or even to distinguish whether the value is $0$ or $1$ (though, I guess, Schanuel’s conjecture or the like might imply that the result cannot be rational at all on exact rational input).  
> **username_0**: Ok, I see! So for the function you propose, separating outputs 0 and 1 would require an exponential precision or an exponential number of digits, which means requiring exponential time if we are using Taylor expansion in particular. Although it seems it is not known yet whether this problem is NP-hard (or worse), state-of-the-art algorithms cannot cope with this problem in polynomial time. Thank you very much, your comments clarified a lot and are a great answer!  

---

## 0 answers

