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$
$\begingroup$
$\endgroup$
1
-
$\begingroup$ I don't really see the connection between your two questions, so I have removed the second one. $\endgroup$– Yuval FilmusOct 21, 2018 at 18:07
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
Your problem is not in P, for two different reasons:
P is a class of decision problems, but your problem is a function problem. Instead of P, you should consider its functional equivalent FP.
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.
answered Oct 21, 2018 at 18:12
-
$\begingroup$ "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$ $\endgroup$ Oct 22, 2018 at 6:42
-
$\begingroup$ 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$. $\endgroup$ Oct 22, 2018 at 6:44
-
$\begingroup$ I'm afraid this doesn't work, since $2^i$ is not polynomial in $i$. $\endgroup$ Oct 22, 2018 at 6:49
-
$\begingroup$ OK, my bad. So, all that we can do is to extract polynomially many least significant bits of $a^b$. $\endgroup$ Oct 22, 2018 at 6:57