A Note on the Complexity of Comparing Succinctly Represented Integers, with an Application to Maximum Probability Parsing

摘要

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 ∈N_+~n; b_1,...,b_n ∈N_+~n; c_1,...,c_m ∈N_+~m; d_1,...,d_m ∈N_+~m; where each of the integers is represented in binary. Problem 1 (equality testing): Decide whether a_1~(b1)a_2~(b2)…a_n~(bn)=c_1~(d1)c_2~(d2)…c_m~(dm). Problem 2 (inequality testing): Decide whether a_1~(b1)a_2~(b2)…a_n~(bn)≥c_1~(d1)c_2~(d2)…c_m~(dm). 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, namely, by Baker and Wuestholz [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 ∈-rules are allowed).