Titre : On the computing power of semialgebraic functions
Exposant : Marcello Mamino
Résumé : We will compare the computing power of variants
of the Blum-Shub-Smale model in which real Turing machines
are endowed with the power to compute certain semialgebraic
functions in one step. For a large class of such
models, we present a characterization of the Boolean parts of time
complexity classes up to polynomial time Turing reduction.