The following two decision problems capture the complexity ofcomparing integers or rationals that are succinctly represented inproduct-of-exponentials notation, or equivalently, via arithmeticcircuits using only multiplication and division gates, and integerinputs:

Input instance: four lists of positive integers:

a1an; b1bn; c1cm; d1dm;

where each of the integers is represented in binary.

Problem 1 (equality testing): Decide whether a1b1a2b2anbn=c1d1c2d2cmdm.

Problem 2 (inequality testing): Decide whether a1b1a2b2anbnc1d1c2d2cmdm .

Problem 1 is easily decidable in polynomial time using a simpleiterative algorithm. Problem 2 is much harder. We observe that thecomplexity of Problem 2 is intimately connected to deep conjecturesand results in number theory. In particular, if a refined form of theABC conjecture formulated by Baker in 1998 holds, or if the olderLang-Waldschmidt conjecture (formulated in 1978) on linear forms inlogarithms holds, then Problem 2 is decidable in P-time (in thestandard Turing model of computation). Moreover, it follows from thebest available quantitative bounds on linear forms in logarithms,e.g., by Baker and W\"{u}stholz (1993) or Matveev (2000), that if mand n are fixed universal constants then Problem 2 is decidable inP-time (without relying on any conjectures).

We describe one application: P-time maximum probability parsing for *arbitrary* stochasticcontext-free grammars (where \epsilon-rules are allowed).