Presburger Arithmetic

[JOSEPH SHIPMAN]

I knew about Vector Addition Systems, but that problem is  too hard! There is a non-elementary lower bound for vector addition systems and an Ackermannian upper bound. The Presburger formulas there aren’t the main source of difficulty.
 
Since deciding Presburger theoremhood can be done in double exponential space and requires at least nondeterministic double exponential time, I’m looking for a natural problem whose best known upper or lower bound is in that range.

— JS

Sent from my iPhone

> On Jul 19, 2022, at 1:34 PM, Erik Winfree <winfree at caltech.edu> wrote:
> 
> Presburger arithmetic comes up naturally in the theory of stochastic discrete chemical reaction networks, specifically, in questions of reachability.  E.g., with some given set of reactions, starting with exactly 17X and 8 Y, is there a series of reactions that might occur to bring the state to being exactly 1 P and 2 Q ?  This problem is (but for notation) identical to or equivalent to reachability questions in Petri Nets and Vector Addition Systems, but for me, the connection to fundament chemistry makes it more “natural”.  The connection to Presburger arithmetic can be found in the extensive and brilliant works of Jérôme Leroux, for example (but also see his more recent work):
> 
> "Vector Addition Systems Reachability Problem (A Simpler Solution)”
> J Leroux - EPiC, 2012
> https://hal.archives-ouvertes.fr/hal-00674970/.  
> 
> For some out-of-date background, forgive me for self-citing:
> "Programmability of chemical reaction networks"
> M Cook, D Soloveichik, E Winfree, J Bruck - Algorithmic bioprocesses, 2009 
> https://link.springer.com/chapter/10.1007/978-3-540-88869-7_27
> 
> And for a more up-to-date view of the connection to chemistry:
> Computing with chemical reaction networks: a tutorial
> R Brijder - Natural Computing, 2019 
> https://link.springer.com/article/10.1007/s11047-018-9723-9
> 
> Of course, I imagine that you may be thinking of “natural” in terms of mathematical naturalness…. and even here I think that the Vector Addition System formulation might serve your purpose.
> 
> Erik
> 
>> On Jul 18, 2022, at 11:19 PM, JOSEPH SHIPMAN <joeshipman at aol.com> wrote:
>> 
>> Does anyone know a natural decidable problem that is equivalent to Presburger Arithmetic? (Presburger Arithmetic has a complexity lower bound of nondeterministic double exponential time and an upper bound of double exponential space).
>> 
>> — JS
>> 
>> Sent from my iPhone
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20220719/5effec8c/attachment.html>