# Does exponentiation reduce to multiplication or the other way around?

Is is more accurate to say that in complexity theory:

$$\text{exponentiation} \leq_p \text{multiplication}$$

or

$$\text{multiplication} \leq_p \text{exponentiation}$$

I understand that if we know how to do multiplication, then we can run multiplication in a loop in polynomial time to get the answer to the exponentiation problem.

But which of the two reflects this? Do we say exponentiation reduces to multiplication (the first one), or the other way around (the second one)?

• Since you understand how to do exponentiation once you have a method for multiplication (you know "how to reduce"), you just need to look closely at the definition for $\Rightarrow_{\text{polynomial}}$ and see how it encompasses your reduction.
– phs
Jan 25 '16 at 19:21
• Related to (but maybe not a duplicate of?) this: cs.stackexchange.com/questions/24691/… Jan 25 '16 at 19:25

Both statements are accurate, assuming $\le_p$ refers to polynomial-time Turing reductions (i.e., Cook reductions), and assuming that in the exponentiation problem, the exponent is specified in unary (otherwise you can't exponentiate in polynomial time). Given an algorithm to multiply in polynomial time, you can use it to exponentiate in polynomial-time via a Turing reduction, since $a^k = a \times a \times \cdots \times a$. Also, given an algorithm to exponentiate in polynomial time, you can use it to multiply in polynomial time via a Turing reduction, since $ab = [(a+b)^2 - a^2 - b^2]/2$. That said, since both multiplication and exponentiation can be computed in polynomial time directly, there's really no need for such a fancy reduction: it's immediate from the definitions that any problem in P reduces to any other problem in P.