36
$\begingroup$

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$} \}$$

$\endgroup$
  • $\begingroup$ I changed the notion "EXP" to "L", since EXP is the name of a famous complexity class, and may lead to confusion. $\endgroup$ – M.S. Dousti Sep 30 '10 at 13:06
  • $\begingroup$ 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. $\endgroup$ – Kaveh Sep 30 '10 at 13:27
  • 3
    $\begingroup$ Sadeq: If you want to avoid complexity classes, L is in no way better than EXP... Changed it to X. $\endgroup$ – Peter Sep 30 '10 at 13:49
  • $\begingroup$ @Peter: In the context, L is most surely a "language" rather than the Log-space complexity class. Anyway, X is a much better choice. $\endgroup$ – M.S. Dousti Sep 30 '10 at 14:27
  • $\begingroup$ @Kaveh: The question states that it is about the exponential function on the natural numbers. $\endgroup$ – Tsuyoshi Ito Sep 30 '10 at 17:12
17
$\begingroup$

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

$\endgroup$
12
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ There is an interesting relation between this answer and mine. If I am not mistaken, a rough overview of the algorithm in [ABKM09] cited in my answer is to combine this idea with the Chinese remainder theorem to obtain higher bits. $\endgroup$ – Tsuyoshi Ito Oct 2 '10 at 16:23
  • $\begingroup$ Ah, I hadn't realised that. $\endgroup$ – Joe Fitzsimons Oct 2 '10 at 17:18
6
$\begingroup$

[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 (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. 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."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.