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

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis

The following two decision problems capture the complexity of comparing integers or rationals that are succinctly represented in product-of-exponentials notation, or equivalently,…