Let $\mathit{PERM\text{-}POWER} = \{ \langle p, q, t\rangle \mid p = q^t \}$ where $p$ and $q$ are permutations on $\{1, \ldots, k\}$ and $t$ is a binary integer. How do I prove that $\mathit{PERM\text{-}POWER}$ is in P?
How to prove perm-power is in P?
0
$\begingroup$
computer-science
computational-complexity
-
1http://en.wikipedia.org/wiki/Exponentiation_by_squaring – 2012-12-11