<p>Here are some upper bounds.</p>

<p>By repeated squaring, the problem is in PSPACE.</p>

<p>There is a slightly better upper bound.  The problem is a special case of the BitSLP problem: Given a straight-line program starting from 0 and 1 with addition, subtraction and multiplication representing an integer <i>N</i>, and given <i>i</i>∈ℕ, decide whether the <i>i</i>-th bit (counting from the least significant bit) of the binary representation of <i>N</i> is 1.  The BitSLP problem is in the counting hierarchy (<a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aC#ch">CH</a>) [ABKM09].  (It is stated in [ABKM09] that it can be shown that the BitSLP problem is in PH<sup>PP<sup>PP<sup>PP<sup>PP</sup></sup></sup></sup>.)</p>

<p>The membership to CH is often considered as an evidence that the problem is unlikely to be PSPACE-hard, because the equality CH=PSPACE implies that the counting hierarchy collapses.  However, I do not know how strong this evidence is considered to be.</p>

<p>As for the hardness, BitSLP is shown to be #P-hard in the same paper [ABKM09].  However, the proof there does not seem to imply any hardness of the language <i>X</i> in the question.</p>

<p>References</p>

<p>[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen and Peter Bro Miltersen.  On the complexity of numerical analysis.  <em>SIAM Journal on Computing</em>, 38(5):1987–2006, Jan. 2009.  <a href="http://dx.doi.org/10.1137/070697926">http://dx.doi.org/10.1137/070697926</a></p>

CC BY-SA 2.5
2010-09-30T17:01:50.987Z
2010-10-03T13:29:21.597Z
2010-10-03T13:29:21.597Z
Tsuyoshi Ito
<p>Not a complete answer, but at least a partial one.</p>

<p>I notice that the two answers that have appeared so far have not mentioned the fact that there is an $O(n^{1+\omega})$ algorithm for calculating the modular exponential $x^y ~\mbox{mod }z$ where $n$ is the number of bits in $z$, and where $\omega$ is the exponent corresponding to the fastest multiplication algorithm. So the less significant bits of the exponential can be calculated efficiently (in $O(n^3)$ or less). </p>

<p>The way to do this is fairly simple: You can compute $c_1 = x$, $c_2 = x^2 ~\mbox{mod }z$, $c_j = c_{j-1}^2 ~\mbox{mod }z$. Clearly $c_j = x^{2^j}~\mbox{mod }z$, and so $x^y \equiv \prod_j c_j^{y_j}~\mbox{mod }z$, but as there are only $n$ terms $c_j$ this takes only $n$ multiplications.</p>

<p>Further, we can write $x^y$ as $(\sum_{i=0}^n 2^i x_i)^y$, so the most significant bits which correspond to roughly $2^{ny}$ can also be efficiently calculate as these will only depend on the on the most significant bit of $x$.</p>

<p>So the only real problem terms are caused by bits towards the center of $x^y$. </p>

CC BY-SA 2.5
2010-10-02T16:23:51.277Z
There is an interesting relation between this answer and mine.  If I am not mistaken, a rough overview of the algorithm in [[ABKM09](http://dx.doi.org/10.1137/070697926)] cited in [my answer](http://cstheory.stackexchange.com/questions/1811/complexity-of-exponential-function/1821#1821) is to combine this idea with the Chinese remainder theorem to obtain higher bits.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-02T17:18:20.203Z
Ah, I hadn't realised that.
Joe Fitzsimons
CC BY-SA 3.0
2010-09-30T15:44:00.037Z
2014-02-20T21:56:33.053Z
2014-02-20T21:56:33.053Z
Joe Fitzsimons
<p>[This answer explains some interesting aspects about <strong>Per Vognsen</strong>'s answer. It is not a direct answer to the OP's question, yet it may help in resolving such questions.]</p>

<p>First, take a look at the following link:
<a href="http://en.wikipedia.org/wiki/Bailey-Borwein-Plouffe_formula">Bailey-Borwein-Plouffe formula</a> (or simply BBP formula). It is a way for calculating the $i$th bit of the irrational number $\pi$, without first computing the first $i-1$ bits. The article points out that BPP-type formulas for other irrational numbers exist, too.</p>

<p>Next, look at Dick Lipton's take on the subject: <a href="http://rjlipton.wordpress.com/2009/03/15/cooks-class-contains-pi/">Cook’s Class Contains Pi</a>. The article essentially describes that deciding the $i$th bit of $\pi$ is in the Steve Cook's class ($\rm SC$, the class of languages accepted in polynomial time and poly-logarithmic space), and that this fact is extraordinarily odd, as he calls it against "conventional wisdom."</p>

<p>PS: At the end of his article, Dick admits that the algorithm might be actually out of $\rm SC$, yet such possibility is beyond "practical use."</p>

CC BY-SA 2.5
2010-09-30T15:16:31.910Z
2010-09-30T15:35:26.190Z
2010-09-30T15:35:26.190Z
Sadeq Dousti
<p>We know that the exponential function $\exp(x,y) = x^y$ over natural numbers is not computable in polynomial time, because the size of the output is not polynomially bounded in the size of the inputs.</p>

<p>Is this the main reason for the difficulty of computing the exponential function, or is exponentiation inherently difficult to compute, independently of this consideration?</p>

<blockquote>
  <p>What is the complexity of the bit graph of the exponential function? 
  $$\{\langle x,y,i \rangle \mid x,y,i\in\mathbb{N} \text{ and the $i$-th bit of $x^y$ is $1$} \}$$</p>
</blockquote>

CC BY-SA 3.0
2011-07-15T17:42:51.797Z
a possibly related paper: [Computing partial information out of intractable: powers of algebraic numbers as an example](http://www.math.tau.ac.il/~rabinoa/pub/power-algebraic.pdf)
Kaveh
CC BY-SA 2.5
2010-09-30T13:06:55.290Z
I changed the notion "EXP" to "L", since EXP is the name of a famous complexity class, and may lead to confusion.
Sadeq Dousti
CC BY-SA 2.5
2010-09-30T13:27:28.200Z
If $x$ is restricted to a power of 2, then $L$ is $AC^0$. Also the graph of the exponentiation $\Gamma exp=\{(x,y,z) : x^y=z\}$ has low complexity.
Kaveh
CC BY-SA 2.5
2010-09-30T13:49:36.927Z
Sadeq: If you want to avoid complexity classes, L is in no way better than EXP... Changed it to X.
Peter
CC BY-SA 2.5
2010-09-30T14:27:57.693Z
@Peter: In the context, L is most surely a "language" rather than the Log-space complexity class. Anyway, X is a much better choice.
Sadeq Dousti
CC BY-SA 2.5
2010-09-30T17:12:06.003Z
@Kaveh: The question states that it is about the exponential function on the natural numbers.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-30T17:40:10.613Z
@Tsuyoshi Ito: Thanks. The answers about $\pi$ confused me.
Kaveh
<cc.complexity-theory><nt.number-theory>
Complexity of exponential function
Peter
# Complexity of exponential function

(Asked by: username_0 on 2010-09-30)

We know that the exponential function $\exp(x,y) = x^y$ over natural numbers is not computable in polynomial time, because the size of the output is not polynomially bounded in the size of the inputs.

Is this the main reason for the difficulty of computing the exponential function, or is exponentiation inherently difficult to compute, independently of this consideration?

> What is the complexity of the bit graph of the exponential function?
> $$\{\langle x,y,i \rangle \mid x,y,i\in\mathbb{N} \text{ and the $i$-th bit of $x^y$ is $1$} \}$$

**Tags:** cc.complexity-theory, nt.number-theory

> **Comments:**
> **username_2**: I changed the notion "EXP" to "L", since EXP is the name of a famous complexity class, and may lead to confusion.  
> **username_1**: If $x$ is restricted to a power of 2, then $L$ is $AC^0$. Also the graph of the exponentiation $\Gamma exp=\{(x,y,z) : x^y=z\}$ has low complexity.  
> **username_0**: Sadeq: If you want to avoid complexity classes, L is in no way better than EXP... Changed it to X.  
> **username_2**: @username_0: In the context, L is most surely a "language" rather than the Log-space complexity class. Anyway, X is a much better choice.  
> **username_3**: @username_1: The question states that it is about the exponential function on the natural numbers.  
> **username_1**: @username_3: Thanks. The answers about $\pi$ confused me.  
> **username_1**: a possibly related paper: [Computing partial information out of intractable: powers of algebraic numbers as an example](http://www.math.tau.ac.il/~rabinoa/pub/power-algebraic.pdf)  

---

## 3 answers

### Answer by username_3 on 2010-09-30. Score: 18

Here are some upper bounds.

By repeated squaring, the problem is in PSPACE.

There is a slightly better upper bound. The problem is a special case of the BitSLP problem: Given a straight-line program starting from 0 and 1 with addition, subtraction and multiplication representing an integer *N*, and given *i*∈ℕ, decide whether the *i*-th bit (counting from the least significant bit) of the binary representation of *N* is 1. The BitSLP problem is in the counting hierarchy ([CH](http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aC#ch)) [ABKM09]. (It is stated in [ABKM09] that it can be shown that the BitSLP problem is in PHPPPPPPPP.)

The membership to CH is often considered as an evidence that the problem is unlikely to be PSPACE-hard, because the equality CH=PSPACE implies that the counting hierarchy collapses. However, I do not know how strong this evidence is considered to be.

As for the hardness, BitSLP is shown to be #P-hard in the same paper [ABKM09]. However, the proof there does not seem to imply any hardness of the language *X* in the question.

References

[ABKM09] Eric Allender, username_0 Bürgisser, Johan Kjeldgaard-Pedersen and username_0 Bro Miltersen. On the complexity of numerical analysis. *SIAM Journal on Computing*, 38(5):1987–2006, Jan. 2009. <http://dx.doi.org/10.1137/070697926>


---

### Answer by username_4 on 2010-09-30. Score: 12

Not a complete answer, but at least a partial one.

I notice that the two answers that have appeared so far have not mentioned the fact that there is an $O(n^{1+\omega})$ algorithm for calculating the modular exponential $x^y ~\mbox{mod }z$ where $n$ is the number of bits in $z$, and where $\omega$ is the exponent corresponding to the fastest multiplication algorithm. So the less significant bits of the exponential can be calculated efficiently (in $O(n^3)$ or less).

The way to do this is fairly simple: You can compute $c\_1 = x$, $c\_2 = x^2 ~\mbox{mod }z$, $c\_j = c\_{j-1}^2 ~\mbox{mod }z$. Clearly $c\_j = x^{2^j}~\mbox{mod }z$, and so $x^y \equiv \prod\_j c\_j^{y\_j}~\mbox{mod }z$, but as there are only $n$ terms $c\_j$ this takes only $n$ multiplications.

Further, we can write $x^y$ as $(\sum\_{i=0}^n 2^i x\_i)^y$, so the most significant bits which correspond to roughly $2^{ny}$ can also be efficiently calculate as these will only depend on the on the most significant bit of $x$.

So the only real problem terms are caused by bits towards the center of $x^y$.

> **Comments:**
> **username_3**: There is an interesting relation between this answer and mine.  If I am not mistaken, a rough overview of the algorithm in [[ABKM09](http://dx.doi.org/10.1137/070697926)] cited in [my answer](http://cstheory.stackexchange.com/questions/1811/complexity-of-exponential-function/1821#1821) is to combine this idea with the Chinese remainder theorem to obtain higher bits.  
> **username_4**: Ah, I hadn't realised that.  

---

### Answer by username_2 on 2010-09-30. Score: 6

[This answer explains some interesting aspects about **Per Vognsen**'s answer. It is not a direct answer to the OP's question, yet it may help in resolving such questions.]

First, take a look at the following link:
[Bailey-Borwein-Plouffe formula](http://en.wikipedia.org/wiki/Bailey-Borwein-Plouffe_formula) (or simply BBP formula). It is a way for calculating the $i$th bit of the irrational number $\pi$, without first computing the first $i-1$ bits. The article points out that BPP-type formulas for other irrational numbers exist, too.

Next, look at Dick Lipton's take on the subject: [Cook’s Class Contains Pi](http://rjlipton.wordpress.com/2009/03/15/cooks-class-contains-pi/). The article essentially describes that deciding the $i$th bit of $\pi$ is in the Steve Cook's class ($\rm SC$, the class of languages accepted in polynomial time and poly-logarithmic space), and that this fact is extraordinarily odd, as he calls it against "conventional wisdom."

PS: At the end of his article, Dick admits that the algorithm might be actually out of $\rm SC$, yet such possibility is beyond "practical use."


---

