Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR13-069 | 1st May 2013 18:33

A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing

TR13-069
Authors: Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
Publication: 3rd May 2013 10:42
Keywords:

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, \ldots , a_n; \ b_1, \ldots ,b_n; \ c_1, \ldots ,c_m; \ d_1, \ldots ,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} \ldots a_n^{b_n} = c_1^{d_1} c_2^{d_2} \ldots c_m^{d_m}$.

Problem 2 (inequality testing): Decide whether
$a_1^{b_1} a_2^{b_2} \ldots a_n^{b_n} \geq c_1^{d_1} c_2^{d_2} \ldots 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).

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

ISSN 1433-8092 | Imprint