  The following two decision problems capture the complexity of comparing
integers or rationals that are succinctly represented in
product-of-exponentials notation, or equivalently, via arithmetic circuits
using only multiplication and division gates, and integer inputs:
  Input instance: four lists of positive integers: a_1, ...., a_n ; b_1,....,
b_n ; c_1,....,c_m ; d_1, ...., d_m ; where each of the integers is represented
in binary.
  Problem 1 (equality testing): Decide whether a_1^{b_1} a_2^{b_2} ....
a_n^{b_n} = c_1^{d_1} c_2^{d_2} .... c_m^{d_m} .
  Problem 2 (inequality testing): Decide whether a_1^{b_1} a_2^{b_2} ...
a_n^{b_n} >= c_1^{d_1} c_2^{d_2} .... c_m^{d_m} .
  Problem 1 is easily decidable in polynomial time using a simple iterative
algorithm. Problem 2 is much harder. We observe that the complexity of Problem
2 is intimately connected to deep conjectures and results in number theory. In
particular, if a refined form of the ABC conjecture formulated by Baker in 1998
holds, or if the older Lang-Waldschmidt conjecture (formulated in 1978) on
linear forms in logarithms holds, then Problem 2 is decidable in P-time (in the
standard Turing model of computation). Moreover, it follows from the best
available quantitative bounds on linear forms in logarithms, e.g., by Baker and
W\"{u}stholz (1993) or Matveev (2000), that if m and n are fixed universal
constants then Problem 2 is decidable in P-time (without relying on any
conjectures). This latter fact was observed earlier by Shub (1993).
  We describe one application: P-time maximum probability parsing for arbitrary
stochastic context-free grammars (where \epsilon-rules are allowed).
