Complexity of exponential function 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$} \}$$
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) [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, Peter Bürgisser, Johan Kjeldgaard-Pedersen and Peter 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