English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

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&ctdot;anbn=c1d1 c2d2&ctdot;cmdm. Problem 2 (inequality testing): Decide whether a1b1 a2b2&ctdot;anbn≥c1d1 c2d2&ctdot;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).

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