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?

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ Surely it will be very fast if you use logarithms! $\endgroup$
    – James Cranch
    Jan 29, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 17:31

1 Answer 1

Reset to default
9
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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