<p>The problem of determining whether a sentence of Presburger arithmetic is true is in between 2-NEXP and 2-EXPSPACE. When the number of quantifier alternations is fixed and at least two, the problem is in between NEXP and EXPSPACE. The existential fragment is NP-complete. For more details, see e.g. <a href="http://www.lsv.fr/~haase/documents/Haase-csllics14.pdf" rel="noreferrer">Christoph Haase, <em>Subclasses of Presburger Arithmetic and the Weak EXP Hierarchy</em>, CSL/LICS 2014.</a></p>

CC BY-SA 3.0
2018-01-04T00:16:15.133Z
2018-01-04T00:16:15.133Z
Michael Blondin
<p>My understanding of the Presburger arithmetic decision problem is that it requires doubly-exponential time, but only singly-exponential space, meaning that it is in $EXPSPACE \setminus EXP$.  Obviously, if this set is not empty, then $P \subsetneq PSPACE$, solving a major open problem, so my understanding is probably wrong.  Where did my reasoning fail?</p>

<cc.complexity-theory><complexity-classes>
Presburger arithmetic: is it known to be in $EXPSPACE \setminus EXP$?
Demi
# Presburger arithmetic: is it known to be in $EXPSPACE \setminus EXP$?

(Asked by: username_0 on 2018-01-03)

My understanding of the Presburger arithmetic decision problem is that it requires doubly-exponential time, but only singly-exponential space, meaning that it is in $EXPSPACE \setminus EXP$. Obviously, if this set is not empty, then $P \subsetneq PSPACE$, solving a major open problem, so my understanding is probably wrong. Where did my reasoning fail?

**Tags:** cc.complexity-theory, complexity-classes

---

## 1 answers

### Answer by username_1 on 2018-01-04. Score: 10

The problem of determining whether a sentence of Presburger arithmetic is true is in between 2-NEXP and 2-EXPSPACE. When the number of quantifier alternations is fixed and at least two, the problem is in between NEXP and EXPSPACE. The existential fragment is NP-complete. For more details, see e.g. [Christoph Haase, *Subclasses of Presburger Arithmetic and the Weak EXP Hierarchy*, CSL/LICS 2014.](http://www.lsv.fr/~haase/documents/Haase-csllics14.pdf)


---

