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 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<F NaN> 6= 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 AR =const = AR , 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: PARR =const = PARR , where PAR stands for parallel polynomial time. In our terminology, we say that R is Asaturated and PAR-saturated. We also prove, at the nonuniform level, the above resul..