Computing over the Reals with Addition and Order: Higher Complexity Classes

This paper deals with issues of structural complexity in a linear version of the Blum-Shub-Smale model of computation over the real numbers. Real versions of PSPACE and of the polynomial time hierarchy are defined, and their properties are investigated. Mainly two types of results are presented: • Equivalence between quantification over the real numbers and over {0, 1}; • Characterizations of recognizable subsets of {0, 1}* in terms of familiar discrete complexity classes. The complexity of the decision and quantifier elimination problems in the theory of the reals with addition and order is also studied. © 1995 Academic Press. All rights reserved.