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.

  • 7
    $\begingroup$ 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. $\endgroup$ Apr 17 '15 at 0:07

Let $~{\mathrm{PRESARITH}}$ denote the decision problem of the truth of statements in Presburger Arithmetic. As you note, [Fischer+Rabin 1974] (PS manuscript) 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.

  • $\begingroup$ How does the nondeterministic time hierarchy theorem even help here? $\;$ $\endgroup$
    – user6973
    Apr 18 '15 at 1:27
  • $\begingroup$ @RickyDemer: I'm not sure why I felt that I needed to reference that; probably was trying to stress a notion of class separations. $\endgroup$ Apr 18 '15 at 5:03
  • $\begingroup$ By "at least $2^{2^{O(n)}}$", do you mean "$2^{2^{\Omega(n)}}$"? $\endgroup$ Apr 18 '15 at 12:09
  • $\begingroup$ @TysonWilliams: yes, edited. $\endgroup$ Apr 18 '15 at 17:12

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&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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.