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?



Comparing two numbers given their factorization
According to [this paper](http://eccc.hpi-web.de/report/2013/069) 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](http://en.wikipedia.org/wiki/Baker%27s_theorem). Of course, it is possible that the version of the problem with $p\_k$ prime is strictly easier than the more general one.


