In this paper we deal with the logical description of complexity classes arising in the real number model of computation introduced by Blum, Shub, and Smale [4]. We adapt the approach of descriptive complexity theory for this model developped in [14] and extend it to capture some further complexity classes over the reals by logical means. Among the latter we find NC$_\mathbb{R}$, PAR$_\mathbb{R}$, EXP$_\mathbb{R}$ and some others more.
Publié le : 1999-03-14
Classification:
03C,
Real Computations,
Descriptive Complexity,
Parallel Algorithms,
03D15,
68Q15,
68Q25,
03C13
@article{1183745711,
author = {Cucker, Felipe and Meer, Klaus},
title = {Logics Which Capture Complexity Classes Over the Reals},
journal = {J. Symbolic Logic},
volume = {64},
number = {1},
year = {1999},
pages = { 363-390},
language = {en},
url = {http://dml.mathdoc.fr/item/1183745711}
}
Cucker, Felipe; Meer, Klaus. Logics Which Capture Complexity Classes Over the Reals. J. Symbolic Logic, Tome 64 (1999) no. 1, pp. 363-390. http://gdmltest.u-ga.fr/item/1183745711/