|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-97-040
Saturation and
Stability in the Theory of Computation over the Reals
Olivier
Chapuis
Universite Lyon I, France
Pascal
Koiran
Ecole Normale Sup\'erieure de Lyon, France
Abstract
This paper was motivated by the following two questions which arise
in the theory of complexity for computation over ordered rings in
the now famous computational model introduced by Blum, Shub and Smale:
(i) is the answer to the question $\p$ $=$? $\np$ the same in every
real-closed field? (ii) if $\p\neq\np$ for $\r$, does there exist
a problem of $\r$ which is $\np$ but not $\np$-complete?
Some unclassical complexity classes arise naturally in the study of
these questions. They are still open, but we could obtain unconditional
results of independent interest. Michaux introduced $/\const$ complexity
classes in an effort to attack question~(i). We show that $\a_{\r}/
\const = \a_{\r}$, answering a question of his. Here $\a$ is the class
of real problems which are algorithmic in bounded time. We also prove
the stronger result: $\parl_{\r}/ \const =\parl_{\r}$, where $\parl$
stands for parallel polynomial time. In our terminology, we say that
$\r$ is $\a$-saturated and $\parl$-saturated. We also prove, at the
nonuniform level, the above results for every real-closed field. It
is not known whether $\r$ is $\p$-saturated. In the case of the reals
with addition and order we obtain $\p$-saturation (and a positive
answer to question (ii)). More generally, we show that an ordered
$\q$-vector space is $\p$-saturated at the nonuniform level (this
almost implies a positive answer to the analogue of question (i)).
We also study a stronger notion that we call $\p$-stability. Blum,
Cucker, Shub and Smale have (essentially) shown that fields of characteristic
0 are $\p$-stable. We show that the reals with addition and order
are $\p$-stable, but real-closed fields are not. Questions (i) and
(ii) and the $/\const$ complexity classes have some model theoretic
flavor. This leads to the theory of complexity over ``arbitrary''
structures as introduced by Poizat. We give a summary of this theory
with a special emphasis on the connections with model theory and we
study $/\const$ complexity classes with this point of view. Note also
that our proof of the $\parl$-saturation of $\r$ shows that an o-minimal
structure which admits quantifier elimination is $\a$-saturated at
the nonuniform level.
Download Compressed Postscript
|