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

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis

Research output: Contribution to journalArticlepeer-review

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:

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 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 Wü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 ε-rules are allowed).
Original languageEnglish
Pages (from-to)9
Number of pages1
JournalACM Transactions on Computation Theory
Volume6
Issue number2
DOIs
Publication statusPublished - 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.

Cite this