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
up vote 7 down vote accepted

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

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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