patternMinor
Is exponentiation in P?
Viewed 0 times
exponentiationstackoverflowprogramming
Problem
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$
Solution
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.
-
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.
Context
StackExchange Computer Science Q#98881, answer score: 7
Revisions (0)
No revisions yet.