4
$\begingroup$

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$
$\endgroup$
  • $\begingroup$ I don't really see the connection between your two questions, so I have removed the second one. $\endgroup$ – Yuval Filmus Oct 21 '18 at 18:07
7
$\begingroup$

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.

$\endgroup$
  • $\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$ – Thinh D. Nguyen Oct 22 '18 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$ – Thinh D. Nguyen Oct 22 '18 at 6:44
  • $\begingroup$ I'm afraid this doesn't work, since $2^i$ is not polynomial in $i$. $\endgroup$ – Yuval Filmus Oct 22 '18 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$ – Thinh D. Nguyen Oct 22 '18 at 6:57

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.