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

DOI10.1145/2601327zbMATH Open1321.68309arXiv1304.5429OpenAlexW2168359059MaRDI QIDQ2943574FDOQ2943574

Authors: Kousha Etessami, Alistair Stewart, Mihalis Yannakakis 

Publication date: 3 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Abstract: 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).

Full work available at URL: https://arxiv.org/abs/1304.5429

Recommendations

• Stochastic context-free grammars, regular languages, and newton's method
• scientific article; zbMATH DE number 1670709
• Complexity of problems of commutative grammars
• Counting problems for Parikh images
• Uniform random generation of words of rational languages

zbMATH Keywords

arithmetic circuitsstochastic context-free grammarslogarithmic formsABC conjectureprobabilistic parsingLang-Waldschmidt conjecturesuccinct representation of numbers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Number-theoretic algorithms; complexity (11Y16)

Cites Work

• Biological Sequence Analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• Derandomizing polynomial identity tests means proving circuit lower bounds
• An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers. II
• Logarithmic forms and group varieties.
• Logarithmic forms and Diophantine geometry
• On the Complexity of Numerical Analysis
• A generalization of Dijkstra's algorithm
• Polynomial time algorithms for multi-type branching processes and stochastic context-free grammars
• Title not available (Why is that?)
• Probabilistic parsing
• Factoring into coprimes in essentially linear time
• Title not available (Why is that?)
• Factor Refinement
• Minorations de Combinaisons Linéaires de Logarithmes de Nombres Algébriques
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (3)

• Title not available (Why is that?)
• On the Order of Power Series and the Sum of Square Roots Problem
• Root separation for trinomials

This page was built for publication: A Note on the Complexity of Comparing Succinctly Represented Integers, with an Application to Maximum Probability Parsing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2943574)