|
NeuroCOLT
Technical Report NC-TR-94-001
Computing over the Reals with Addition and Order:
Higher Complexity Classes
Felipe
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.
Download Compressed Postscript
|