Presburger open questions

[JOSEPH SHIPMAN]

There are some questions which can be expressed in decidable theories, but to which we don’t know the answer for reasons of computational complexity.

For example, one can express various problems of geometry (sphere packing and so on) in the first order theory of the real numbers which is decidable by Tarski.

Presburger Arithmetic (the theory of the addition of natural numbers) is decidable, with complexity in between double exponential nondeterministic time and double exponential space. Is there any open question mathematicians care about which can be shown to be equivalent to a specific Presburger formula?

— JS

Sent from my iPhone