The complexity of comparing a power to some threshold Consider the following simple problem:


  Given fractions $a/b$, $c/d$ with $a/b&lt;1$ and $c/d&lt;1$, and natural
  number $e$, both encoded in binary (so the problem size is
  $\log(a)+\log(b)+\log(c)+\log(d)+\log(e)$, decide whether
  $$(\frac{a}{b})^e \geq \frac{c}{d}$$.


What's the precise complexity of this problem? Note that one can simply compute $(\frac{a}{b})^e$, as it might require $e\cdot (\log(a)+\log(b))$ bits to store. 

Any upper/lower bound? Do I miss something here?
The problem is decidable in polynomial time (in fact, in uniform $\mathrm{TC}_0$). We can recast the question as follows: given positive integers $a,b,c,d,e$, find the sign of
$$\Lambda=e\log(a/b)-\log(c/d).$$
First, note that we can test whether $\Lambda=0$: if we assume w.l.o.g. that $\gcd(a,b)=\gcd(c,d)=1$, then $da^e=cb^e$ implies $a^e\mid c$ and $b^e\mid d$; in particular, apart from the trivial case $a=b=1$, equality can hold only if $e\le\max\{\log c,\log d\}$, in which case we can evaluate $a^e,b^e$ in polynomial time.

Likewise, we can rule out the case when $(a/b)^{e_1}=(c/d)^{e_2}$ for some positive integers $e_1,e_2$. The argument above shows that if this is the case, then $e_1,e_2\le\max\{\log a,\log b,\log c,\log d\}$, hence we can find $e_1,e_2$ by brute force in polynomial time, and then it suffices to compare $e$ with $e_1/e_2$.

Thus, suppose $a/b$ is not a rational power of $c/d$, which implies $\Lambda\ne0$. Write $\alpha_1=a/b$, $\alpha_2=c/d$, $\lambda_1=\log\alpha_1$, $\lambda_2=\log\alpha_2$, $\beta_1=e$, $\beta_2=-1$. Note that the logarithmic height $h(\alpha_1)=\max\{\log a,\log b\}$, $h(\alpha_2)=\max\{\log c,\log d\}$, and $\lambda_1,\lambda_2$ are linearly independent over $\mathbb Q$. By some version of Baker’s theorem (e.g., the “explicit result by Baker and Wüstholz” in http://en.wikipedia.org/wiki/Baker%27s_theorem#Statement), we have

$$\log\lvert\Lambda\rvert&gt;-Ch(\alpha_1)h(\alpha_2)\log\beta_1$$

for some constant $C$ (note that in the statement given in the link, we have $n=2$ and $d=1$, hence $C$ is really independent of the input data). The number on the right-hand side is polynomial in the length of the input, and it thus suffices to approximately evaluate $\Lambda$ with polynomially many bits of precision, which can be done by standard numerical algorithms in polynomial time.

(If you want to look for more information, the keyword is “linear forms in logarithms”.)