<p>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.</p>

<p>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$.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Baker%27s_theorem#Statement" rel="nofollow">http://en.wikipedia.org/wiki/Baker%27s_theorem#Statement</a>), we have</p>

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

<p>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.</p>

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

CC BY-SA 3.0
2012-07-24T17:46:58.230Z
very nice use of baker's theorem. btw, a very readable proof of a special of the theorem by terry tao: http://terrytao.wordpress.com/2011/08/21/hilberts-seventh-problem-and-powers-of-2-and-3/
Sasho Nikolov
CC BY-SA 3.0
2012-07-24T14:00:04.097Z
2012-07-24T16:44:22.440Z
2012-07-24T16:44:22.440Z
Emil Jeřábek
<p>Consider the following simple problem:</p>

<blockquote>
  <p>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}$$.</p>
</blockquote>

<p>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. </p>

<p>Any upper/lower bound? Do I miss something here?</p>

CC BY-SA 3.0
2012-07-13T23:08:28.180Z
if $a^b$ requires more than $\log c$ bits to store, then it is bigger than $c$... what kind of answer do you expect?
Artem Kaznatcheev
CC BY-SA 3.0
2012-07-13T23:25:42.997Z
thanks Artem. I edited the problem; the original formulation is not correct.
maomao
CC BY-SA 3.0
2012-07-14T04:02:04.153Z
I think there was a similar question sometime ago, I couldn't find it right now.
Kaveh
CC BY-SA 3.0
2012-07-14T16:19:49.607Z
If you take the log of both sides, then you are just asking if $e (\log a - \log b) \ge \log c - \log d$.
Tyson Williams
CC BY-SA 3.0
2012-07-14T18:13:41.180Z
Tyson, thanks. But the problem of your solution is that how to compute log(a), log(b) ... they are in general real numbers, you can only compute the rational approximations, then how many bits do you need to compute? It is not clear how a polynomial algorithm can be obtained.
maomao
CC BY-SA 3.0
2012-07-15T21:25:47.873Z
What, precisely, are you looking for?  If $\log(c) + \log(d) \approx e \cdot (\log(a) + \log(b))$, I don't see any more efficient (deterministic) way to test the inequality.  You can, of course, just keep exponentiating $(\frac{a}{b})$ until you hit $e$ or you exceed $(\frac{c}{d})$.  Are you looking for something more efficient in terms of the number of bits of $a$, $b$, $c$ and $d$?  Are you looking to optimize for space?  For speed?  In terms of the relative sizes of each of the numbers?
user834
CC BY-SA 3.0
2012-07-15T22:23:50.837Z
I am looking for a polynomial-time algorithm, or some argument saying this is not likely. (For instance, showing this problem is NP-hard, or reducing some long-standing open problem to this one, etc)
maomao
CC BY-SA 3.0
2012-07-15T22:56:46.317Z
What's known about the following special case: "Given positive integers $x$ and $y$, is $2^x \ge y$?"
Jeffε
CC BY-SA 3.0
2012-07-16T12:23:15.487Z
@JɛﬀE: This is trivially in P, just count the number of digits in $y$. Even if the base $b$ of the exponentiation is different from the base of the representation, the problem is in P: if $x$ is larger that an estimate of $\log_by$ based on the number of digits, the answer is yes. Otherwise, $b^x$ is sufficiently small so that you can evaluate in in polynomial time.
Emil Jeřábek
CC BY-SA 3.0
2012-07-16T19:09:21.593Z
@Emil, the reference you give can decide whether the sum of radicals is equal to 0, or decide whether it is a rational. I do not see how it solves the problem posted here.
maomao
CC BY-SA 3.0
2012-07-16T23:33:15.867Z
@Ricky, that is true, however to verify $d\cdot a^e-c\cdot b^e\geq 0$, one might need to compute many many bits. It is not clear how to do this in polynomial time.
maomao
CC BY-SA 3.0
2012-07-16T23:36:18.810Z
I think it would be interesting to think whether one could reduce some well-known open problem to this problem as an argument that this problem is very hard. For instance, is it possible to reduce the square-root-sum problem (decide whether $\sum_{i=1}^n \sqrt{a_i}\leq b$ for intergers $a_i$ and $b$?
maomao
CC BY-SA 3.0
2012-07-17T02:44:06.180Z
am i missing something here: say $e$ is a power of 2 (it's not hard to remove this assumption imo). one can repeatedly square $a/b$ until it either exceeds $c/d$ or $(a/b)^e$ is reached. clearly the space/time used is polynomial in $\log{(c)} + \log{(d)}$
Sasho Nikolov
CC BY-SA 3.0
2012-07-17T14:17:48.463Z
@Sasho: Exact representation of $(a/b)^e$ takes $O((\log a+\log b)e)$ bits, and it can be exponentially larger than $\log c+\log d$ even if the *value* of $(a/b)^e$ is smaller than $c/d$.
Emil Jeřábek
CC BY-SA 3.0
2012-07-17T19:37:27.457Z
Maybe useful to think of a special case when $a=1$. We are then asking whether $d \ge c b^e$. Note that $b$ is an integer $\ge 2$. Hence $b^e$ has roughly $e \log b$ bits. If $d$ has fewer bits than this then the answer is no. Otherwise we can afford to evaluate $b^e$ exactly and compare.
Chandra Chekuri
CC BY-SA 3.0
2012-07-18T04:15:30.753Z
Doesn't Emil's answer to Jeff's question handle this case as well ?
Suresh Venkat
CC BY-SA 3.0
2012-07-18T15:55:08.317Z
Yes, it does, did not realize it. Continuing the same thought process. We want to know if $d \ge c (1+x)^e$ where $x = (b-a)/a$. If $x > \epsilon$ for some small but fixed constant then the previous argument applies. Otherwise we can estimate the # of bits of the integer portion of rhs as $\log c + e x$ (to constant factors). If $\log d$ is too big or small compared to this we are done. Otherwise we know that the precision to which we need to evaluate $(1+x)^e$ is about $\log d$ bits which is poly in input size. This is probably doable??
Chandra Chekuri
CC BY-SA 3.0
2012-07-18T18:04:31.910Z
It is one thing to evaluate $y=c(1+x)^e$ to $k=\log d$ bits in the sense of computing $(1+\epsilon)y$ for some $-2^{-k}<\epsilon<2^{-k}$, which is doable, and another thing to compute, exactly, the first $k$ bits of $y$, which is what we need.
Emil Jeřábek
CC BY-SA 3.0
2012-07-18T18:19:31.097Z
@EmilJeřábek, yes, it is not clear to me. Lets simplify the question further. Suppose $c=1$ and $b-a=1$. Then we are asking if $d \ge (1+1/a)^e$. Can be solve this? We know that $e/a$ is roughly $\log d$ so $e=a \log d$. But $e$ and $a$ can be quite large. I find this question very interesting and am trying to see if one can say some thing via elementary means or not.
Chandra Chekuri
CC BY-SA 3.0
2012-07-18T20:40:25.090Z
Elementary functions such as $\ln(x)$, $\exp(x)$ etc can be evaluated to $t$ digits of precision for a rational number $x$ where the running time is polynomial in size of $x$ and $t$. See here for pointers. http://mathoverflow.net/questions/19946/what-is-the-time-complexity-of-computing-sinx-to-t-bits-of-precision. It appears that one can use those results to evaluate $c(1+x)^e$ to $\log d$ bits of precision by first evaluating $\ln (b/a)$ to a precision of $\Omega(\log e + \log d)$ bits then computing $\exp(e \ln(b/a)$ to $\log d$ bits of precision.
Chandra Chekuri
<cc.complexity-theory>
The complexity of comparing a power to some threshold
maomao
# The complexity of comparing a power to some threshold

(Asked by: username_0 on 2012-07-13)

Consider the following simple problem:

> Given fractions $a/b$, $c/d$ with $a/b<1$ and $c/d<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?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: if $a^b$ requires more than $\log c$ bits to store, then it is bigger than $c$... what kind of answer do you expect?  
> **username_0**: thanks Artem. I edited the problem; the original formulation is not correct.  
> **username_2**: I think there was a similar question sometime ago, I couldn't find it right now.  
> **username_3**: If you take the log of both sides, then you are just asking if $e (\log a - \log b) \ge \log c - \log d$.  
> **username_0**: Tyson, thanks. But the problem of your solution is that how to compute log(a), log(b) ... they are in general real numbers, you can only compute the rational approximations, then how many bits do you need to compute? It is not clear how a polynomial algorithm can be obtained.  
> **username_4**: What, precisely, are you looking for?  If $\log(c) + \log(d) \approx e \cdot (\log(a) + \log(b))$, I don't see any more efficient (deterministic) way to test the inequality.  You can, of course, just keep exponentiating $(\frac{a}{b})$ until you hit $e$ or you exceed $(\frac{c}{d})$.  Are you looking for something more efficient in terms of the number of bits of $a$, $b$, $c$ and $d$?  Are you looking to optimize for space?  For speed?  In terms of the relative sizes of each of the numbers?  
> **username_0**: I am looking for a polynomial-time algorithm, or some argument saying this is not likely. (For instance, showing this problem is NP-hard, or reducing some long-standing open problem to this one, etc)  
> **username_5**: What's known about the following special case: "Given positive integers $x$ and $y$, is $2^x \ge y$?"  
> **username_6**: @JɛﬀE: This is trivially in P, just count the number of digits in $y$. Even if the base $b$ of the exponentiation is different from the base of the representation, the problem is in P: if $x$ is larger that an estimate of $\log_by$ based on the number of digits, the answer is yes. Otherwise, $b^x$ is sufficiently small so that you can evaluate in in polynomial time.  
> **username_0**: @Emil, the reference you give can decide whether the sum of radicals is equal to 0, or decide whether it is a rational. I do not see how it solves the problem posted here.  
> **username_0**: @Ricky, that is true, however to verify $d\cdot a^e-c\cdot b^e\geq 0$, one might need to compute many many bits. It is not clear how to do this in polynomial time.  
> **username_0**: I think it would be interesting to think whether one could reduce some well-known open problem to this problem as an argument that this problem is very hard. For instance, is it possible to reduce the square-root-sum problem (decide whether $\sum_{i=1}^n \sqrt{a_i}\leq b$ for intergers $a_i$ and $b$?  
> **username_7**: am i missing something here: say $e$ is a power of 2 (it's not hard to remove this assumption imo). one can repeatedly square $a/b$ until it either exceeds $c/d$ or $(a/b)^e$ is reached. clearly the space/time used is polynomial in $\log{(c)} + \log{(d)}$  
> **username_6**: @Sasho: Exact representation of $(a/b)^e$ takes $O((\log a+\log b)e)$ bits, and it can be exponentially larger than $\log c+\log d$ even if the *value* of $(a/b)^e$ is smaller than $c/d$.  
> **username_8**: Maybe useful to think of a special case when $a=1$. We are then asking whether $d \ge c b^e$. Note that $b$ is an integer $\ge 2$. Hence $b^e$ has roughly $e \log b$ bits. If $d$ has fewer bits than this then the answer is no. Otherwise we can afford to evaluate $b^e$ exactly and compare.  
> **username_9**: Doesn't Emil's answer to Jeff's question handle this case as well ?  
> **username_8**: Yes, it does, did not realize it. Continuing the same thought process. We want to know if $d \ge c (1+x)^e$ where $x = (b-a)/a$. If $x > \epsilon$ for some small but fixed constant then the previous argument applies. Otherwise we can estimate the # of bits of the integer portion of rhs as $\log c + e x$ (to constant factors). If $\log d$ is too big or small compared to this we are done. Otherwise we know that the precision to which we need to evaluate $(1+x)^e$ is about $\log d$ bits which is poly in input size. This is probably doable??  
> **username_6**: It is one thing to evaluate $y=c(1+x)^e$ to $k=\log d$ bits in the sense of computing $(1+\epsilon)y$ for some $-2^{-k}<\epsilon<2^{-k}$, which is doable, and another thing to compute, exactly, the first $k$ bits of $y$, which is what we need.  
> **username_8**: @EmilJeřábek, yes, it is not clear to me. Lets simplify the question further. Suppose $c=1$ and $b-a=1$. Then we are asking if $d \ge (1+1/a)^e$. Can be solve this? We know that $e/a$ is roughly $\log d$ so $e=a \log d$. But $e$ and $a$ can be quite large. I find this question very interesting and am trying to see if one can say some thing via elementary means or not.  
> **username_8**: Elementary functions such as $\ln(x)$, $\exp(x)$ etc can be evaluated to $t$ digits of precision for a rational number $x$ where the running time is polynomial in size of $x$ and $t$. See here for pointers. http://mathoverflow.net/questions/19946/what-is-the-time-complexity-of-computing-sinx-to-t-bits-of-precision. It appears that one can use those results to evaluate $c(1+x)^e$ to $\log d$ bits of precision by first evaluating $\ln (b/a)$ to a precision of $\Omega(\log e + \log d)$ bits then computing $\exp(e \ln(b/a)$ to $\log d$ bits of precision.  

---

## 1 answers

### Answer by username_6 on 2012-07-24. Score: 5

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>-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”.)

> **Comments:**
> **username_7**: very nice use of baker's theorem. btw, a very readable proof of a special of the theorem by terry tao: http://terrytao.wordpress.com/2011/08/21/hilberts-seventh-problem-and-powers-of-2-and-3/  

---

