@inproceedings{2aa987d9997d4126bd792b8a4e1f3f91,
title = "On the complexity of some problems for the Blum, Shub \& Smale model",
abstract = "We show some problems deriving from real algebra and semialgebraic geometry to be NP-complete or coNP-complete for the Blum, Shub and Smale model of computation. We also introduce a class of languages R lying between P and NP that uses probabilistic machines, and several problems from the same area are classified as “probably noncomplete” by showing their membership in R.",
author = "Felipe Cucker and Francesc Rossell{\'o}",
year = "1992",
month = apr,
doi = "10.1007/BFb0023823",
language = "English",
isbn = "978-3-540-55284-0",
series = "Lecture Notes in Computer Science",
publisher = "Springer Verlag",
pages = "117--129",
editor = "I. Simon",
booktitle = "LATIN '92",
address = "Germany",
note = "1st Latin American Symposium on Theoretical Informatics (LATIN '92) ; Conference date: 06-04-1992 Through 10-04-1992",
}