0
$\begingroup$

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?

  • 1
    http://en.wikipedia.org/wiki/Exponentiation_by_squaring2012-12-11

1 Answers 1