<p>Let $~{\mathrm{PRESARITH}}$ denote the decision problem of the truth of statements in Presburger Arithmetic. As you note, [Fischer+Rabin&nbsp;1974] (<a href="http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps" rel="nofollow">PS manuscript</a>) show that the nondeterministic time complexity of $\mathrm{PRESARITH}$ is at least $2^{2^{\Omega(n)}}$. In particular, $\mathrm{PRESARITH} \notin \mathsf{NEXP}$.
However, we have the containments
$$ \mathsf{
BPP \;\subseteq\; BQP \;\subseteq\; PP \;\subseteq\; PSPACE \;\subseteq\; EXP \;\subseteq\; NEXP
}
$$</p>

<p>Thus, it directly follows that $\mathrm{PRESARITH} \notin \mathsf{BQP}$, and in particular it is not in $\mathsf{BPP}$ either.</p>

CC BY-SA 3.0
2015-04-18T05:03:38.613Z
@RickyDemer: I'm not sure why I felt that I needed to reference that; probably was trying to stress a notion of class separations.
Niel de Beaudrap
CC BY-SA 3.0
2015-04-18T12:09:18.443Z
By "at least $2^{2^{O(n)}}$", do you mean "$2^{2^{\Omega(n)}}$"?
Tyson Williams
CC BY-SA 3.0
2015-04-18T17:12:41.600Z
@TysonWilliams: yes, edited.
Niel de Beaudrap
CC BY-SA 3.0
2015-04-17T00:05:21.893Z
2015-04-18T17:12:14.943Z
2015-04-18T17:12:14.943Z
Niel de Beaudrap
<p>Niel de Beaudrap answered the question as such, but let me mention for the record that the complexity of Presburger arithmetic is known more precisely than the Fischer&amp;Rabin bound: full Presburger arithmetic is complete for alternating doubly exponential time with a linear number of alternations (due to Berman), and the $\Sigma_{i+1}$-fragment is complete for $\Sigma_i^{EXP}$ (<a href="http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/Haase-csllics14.pdf">Haase</a>).</p>

CC BY-SA 3.0
2015-04-17T20:20:44.890Z
2015-04-17T20:20:44.890Z
Emil Jeřábek
<p>Presburger arithmetic is well-known to be decidable but intractable, requiring doubly exponential time even with nondeterminism (Fischer and Rabin, 1974).  I am wondering if it is also known whether the Presburger arithmetic decision problem remains intractable with quantum computation or even just randomized computation, and specifically whether it falls outside of BQP or BPP.  It would be profoundly humbling if such a seemingly weak mathematical theory, which doesn't even allow multiplication, gives rise to provably intractable problems.</p>

CC BY-SA 3.0
2015-04-17T00:07:47.037Z
The fact that it has at least doubly-exponential nondeterministic time complexity is already humbling, and basically tells the whole story. The enthusiastic waxing of technologists and science journalists aside, we don't expect quantum computation to be able to solve problems even with a *singly exponential deterministic* lower bound, or even many problems with a *polynomial-time nondeterministic* upper bound. So your first intuition should immediately be that this problem is intractible for quantum (and randomized) algorithms, which is indeed the case.
Niel de Beaudrap
<cc.complexity-theory><quantum-computing>
Is the Presburger arithmetic decision problem known to be outside of BQP or BPP?
Anonymous
# Is the Presburger arithmetic decision problem known to be outside of BQP or BPP?

(Asked by: username_0 on 2015-04-16)

Presburger arithmetic is well-known to be decidable but intractable, requiring doubly exponential time even with nondeterminism (Fischer and Rabin, 1974). I am wondering if it is also known whether the Presburger arithmetic decision problem remains intractable with quantum computation or even just randomized computation, and specifically whether it falls outside of BQP or BPP. It would be profoundly humbling if such a seemingly weak mathematical theory, which doesn't even allow multiplication, gives rise to provably intractable problems.

**Tags:** cc.complexity-theory, quantum-computing

> **Comments:**
> **username_1**: The fact that it has at least doubly-exponential nondeterministic time complexity is already humbling, and basically tells the whole story. The enthusiastic waxing of technologists and science journalists aside, we don't expect quantum computation to be able to solve problems even with a *singly exponential deterministic* lower bound, or even many problems with a *polynomial-time nondeterministic* upper bound. So your first intuition should immediately be that this problem is intractible for quantum (and randomized) algorithms, which is indeed the case.  

---

## 2 answers

### Answer by username_1 on 2015-04-17. Score: 11

Let $~{\mathrm{PRESARITH}}$ denote the decision problem of the truth of statements in Presburger Arithmetic. As you note, [Fischer+Rabin 1974] ([PS manuscript](http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps)) show that the nondeterministic time complexity of $\mathrm{PRESARITH}$ is at least $2^{2^{\Omega(n)}}$. In particular, $\mathrm{PRESARITH} \notin \mathsf{NEXP}$.
However, we have the containments
$$ \mathsf{
BPP \;\subseteq\; BQP \;\subseteq\; PP \;\subseteq\; PSPACE \;\subseteq\; EXP \;\subseteq\; NEXP
}
$$

Thus, it directly follows that $\mathrm{PRESARITH} \notin \mathsf{BQP}$, and in particular it is not in $\mathsf{BPP}$ either.

> **Comments:**
> **username_1**: @RickyDemer: I'm not sure why I felt that I needed to reference that; probably was trying to stress a notion of class separations.  
> **username_2**: By "at least $2^{2^{O(n)}}$", do you mean "$2^{2^{\Omega(n)}}$"?  
> **username_1**: @TysonWilliams: yes, edited.  

---

### Answer by username_3 on 2015-04-17. Score: 7

username_1 answered the question as such, but let me mention for the record that the complexity of Presburger arithmetic is known more precisely than the Fischer&Rabin bound: full Presburger arithmetic is complete for alternating doubly exponential time with a linear number of alternations (due to Berman), and the $\Sigma\_{i+1}$-fragment is complete for $\Sigma\_i^{EXP}$ ([Haase](http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/Haase-csllics14.pdf)).


---

