11
$\begingroup$

I'm not an expert, but given the integer factorization of two numbers $a,b$:

$$a = p_{i_1}^{a_1}...p_{i_n}^{a_n}, \quad b = p_{j_1}^{b_1}...p_{j_m}^{b_m}$$

What is the time and space compexity of checking if $a > b$ ?

Suppose that the factors and the exponents are given in binary and the whole input over alphabet $\{0,1,\wedge,;,*\}$ looks like: $$p_{i_1}\wedge{a_1}*...*p_{i_n}\wedge{a_n};p_{j_1}\wedge{b_1}*...*p_{j_m}\wedge{b_m}$$

What algorithms can be used?

$\endgroup$
  • 2
    $\begingroup$ Surely it will be very fast if you use logarithms! $\endgroup$ – James Cranch Jan 29 '14 at 16:52
  • 1
    $\begingroup$ First compute using logarithms. That will either resolve the issue quickly, or it will tell you a precision you need for the next step. If the logs say the numbers agree except perhaps for the last m digits in base b, then multiply (the factorizations of) both numbers modulo b^{m+c}, where c is either 1 or 2 or small enough to be worth the trouble and large enough to decide the issue. $\endgroup$ – The Masked Avenger Jan 29 '14 at 16:55
  • 4
    $\begingroup$ @TheMaskedAvenger: Don't you need to invoke something like Baker's Theorem to show that the details will work out, i.e. you won't have to compute exponentially many bits of the logarithms before concluding? (I haven't checked -- do these details work out?) $\endgroup$ – Noah Stein Jan 29 '14 at 17:12
  • 5
    $\begingroup$ @NoahStein: You are perfectly right. Since the exponent are given in binary, one might in principle need exponentially many bits to resolve the inequality using logarithms. A similar question was posted here: cstheory.stackexchange.com/questions/12029/… $\endgroup$ – Emil Jeřábek Jan 29 '14 at 17:26
  • 2
    $\begingroup$ Note that even without Baker’s theorem, the problem is solvable in polynomial space, as it is reducible to the existential theory of the reals: one can simulate the computation of $p_i^{a_i}$ by repeated squaring using linearly many existential quantifiers. $\endgroup$ – Emil Jeřábek Jan 29 '14 at 17:31
8
$\begingroup$

According to this paper from 2013 by Etessami, Stewart, and Yannakakis, the time complexity of the [a priori] harder problem where the $p_k$ are not required to be prime is still open. In that paper the authors show that certain conjectures in number theory would imply that the simple algorithm ("compute enough bits of the logs") runs in polynomial time. The authors also observe that unconditional on any conjectures the algorithm runs in polynomial time for fixed $m$ and $n$ by Baker's Theorem. Of course, it is possible that the version of the problem with $p_k$ prime is strictly easier than the more general one.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.