Saturation and stability in the theory of computation over the reals

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 c omputational model introduced by Blum, Shub and Smale: (i) is the answer to the question P = ?NP the same in every real-closed fie ld? (ii) if P not equal NP for (FS, does there exist a problem of R which is NP but neither P nor NP-complete? Some unclassical complexity classes arise naturally in the study of these q uestions. They are still open, but we could obtain unconditional results of independent interest. Michaux introduced /const complexity classes in an effort to attack questio n (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 als o prove the stronger result: PAR(R)/const = PAR(R), where PAR stands for pa rallel polynomial time. In our terminology, we say that R is A-saturated an d PAR-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 t he case of the reals with addition and order we obtain P-saturation land 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, Shu b 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 re al-closed fields are not. Questions (i) and (ii) and the /const complexity classes have some model th eoretic flavor. This leads to the theory of complexity over "arbitrary" str uctures as introduced by Poizat. We give a summary of this theory with a sp ecial emphasis on the connections with model theory and we study /const com plexity classes from this point of view. Note also that our proof of the PA R-saturation of R shows that an o-minimal structure which admits quantifier elimination is A-saturated at the nonuniform level. (C) 1999 Elsevier Scie nce B.V. All rights reserved.