Presburger Arithmetic

JOSEPH SHIPMAN joeshipman at
Tue Jul 19 02:19:41 EDT 2022

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

More information about the FOM mailing list