DIMACS TR: 94-08

Computing over the reals with addition and order: higher complexity classes



Authors: Flipe Cucker and Pascal Koiran

ABSTRACT

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.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-08.ps

DIMACS Home Page