Abstract
The following two decision problems capture the complexity of comparing integers or rationals that are succinctly represented in productofexponentials notation, or equivalently, via arithmetic circuits using only multiplication and division gates, and integer inputs. Input instance: Four lists of positive integers:
a1,..., an∈N+n; b1,...,bn∈N+n; c1,...,cm∈N+m; d1, ..., dm∈N+m;
where each of the integers is represented in binary.
Problem 1 (equality testing): Decide whether a1b1 a2b2⋯anbn=c1d1 c2d2⋯cmdm.
Problem 2 (inequality testing): Decide whether a1b1 a2b2⋯anbn≥c1d1 c2d2⋯cmdm.
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 LangWaldschmidt conjecture (formulated in 1978) on linear forms in logarithms holds, then Problem 2 is decidable in Ptime (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 Wüstholz [1993] or Matveev [2000], that if m and n are fixed universal constants then Problem 2 is decidable in Ptime (without relying on any conjectures). This latter fact was observed earlier by Shub [1993].
We describe one application: Ptime maximum probability parsing for arbitrary stochastic contextfree grammars (where εrules are allowed).
a1,..., an∈N+n; b1,...,bn∈N+n; c1,...,cm∈N+m; d1, ..., dm∈N+m;
where each of the integers is represented in binary.
Problem 1 (equality testing): Decide whether a1b1 a2b2⋯anbn=c1d1 c2d2⋯cmdm.
Problem 2 (inequality testing): Decide whether a1b1 a2b2⋯anbn≥c1d1 c2d2⋯cmdm.
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 LangWaldschmidt conjecture (formulated in 1978) on linear forms in logarithms holds, then Problem 2 is decidable in Ptime (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 Wüstholz [1993] or Matveev [2000], that if m and n are fixed universal constants then Problem 2 is decidable in Ptime (without relying on any conjectures). This latter fact was observed earlier by Shub [1993].
We describe one application: Ptime maximum probability parsing for arbitrary stochastic contextfree grammars (where εrules are allowed).
Original language  English 

Pages (fromto)  9 
Number of pages  1 
Journal  ACM Transactions on Computation Theory 
Volume  6 
Issue number  2 
DOIs  
Publication status  Published  2014 
Fingerprint
Dive into the research topics of 'A Note on the Complexity of Comparing Succinctly Represented Integers, with an Application to Maximum Probability Parsing'. Together they form a unique fingerprint.Profiles

Kousha Etessami
 School of Informatics  Personal Chair in Algorithms, Games, Logic and Complexity
 Laboratory for Foundations of Computer Science
 Foundations of Computation
Person: Academic: Research Active