"The theory of reals with addition (see EXPSPACE) is hard for NEXP"

M. J. Fischer and M. O. Rabin. Super-exponential complexity of Presburger arithmetic, Complexity of Computation (R. M. Karp, ed.), SIAM-AMS Symposium on Applied Mathematics, 1974.

‏¹ http://qwiki.stanford.edu/wiki/Complexity_Zoo#nexp