# Is exponentiation in P?

I think the following problem belong to class P, but I don't know how I can prove it, could somebody help me?

• Inputs: two numbers $$(a,b) \in \mathbb{N}$$
• Output: $$a^b$$
• I don't really see the connection between your two questions, so I have removed the second one. – Yuval Filmus Oct 21 at 18:07

Your problem is not in P, for two different reasons:

1. P is a class of decision problems, but your problem is a function problem. Instead of P, you should consider its functional equivalent FP.

2. The output could be exponentially large in the input length: encoding $$b$$ takes about $$\log b$$ bits, but encoding $$a^b$$ takes about $$b \log a$$ bits.

This still leaves open the possibility that the following problem is in P:

Given natural numbers $$a,b$$ and an index $$i$$, determine the $$i$$th bit of $$a^b$$.

While I don't know what the answer to this question is, here is a related problem in FP:

Given natural numbers $$a,b,c$$, determine $$a^b \bmod c$$.

This can be shown using the important technique of repeated squaring.

• "This still leaves open the possibility that the following problem is in P: Given natural numbers $a,b$ and an index $i$, determine the $i$th bit of $a^b$". This is not open, and is in $P$ by your problem in FP: Given natural numbers $a,b,c$, determine $a^b\ \mathrm{mod}\ c$ and set $c=2^i$ – Thinh D. Nguyen Oct 22 at 6:42
• Also, if $i$ is the index from the left (more significant digit, in big endian), then a careful base conversion that involves floating-point arithmetics could determine the number of bits in binary representation of $a^b$. – Thinh D. Nguyen Oct 22 at 6:44
• I'm afraid this doesn't work, since $2^i$ is not polynomial in $i$. – Yuval Filmus Oct 22 at 6:49
• OK, my bad. So, all that we can do is to extract polynomially many least significant bits of $a^b$. – Thinh D. Nguyen Oct 22 at 6:57