Skip Navigation

The Computer Journal 1993 36(5):400-408; doi:10.1093/comjnl/36.5.400
© 1993 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (13)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Cucker, F.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

On the Complexity of Quantifier Elimination: the Structural Approach

F. Cucker *

Universitat Pompeu Fabra, c/ Balmes 132, Barcelona 08008, Spain

The aim of this paper is to survey certain theoretical aspects of the complexity of quantifier elimination in the elementary theory of the real numbers with real constants, and to present some new results on the subject. We use the new model of computation introduced by L. Blum, M. Shub and S. Smale that accepts as inputs vectors of real numbers and allows the transfer of the structural approach to computability and complexity for computations with real numbers. More concretely, we give a proof of the existence of NPR-complete problems. Also, we introduce a new complexity class PATR which describes the complexity of the decision of quantified formulae and, in order to study its relationship with the already existing complexity classes, a model for parallel computations is also introduced. Using the classes resulting by bounding resources in this parallel model, some separation results are finally obtained. In particular, we show that the polynomial hierarchy overs the reals is strictly contained in PATR.

Received December 1992. revised April 1993.

* Partially supported by the ESPRIT BRA Programs of the EC n. 7141 and 6546, projects ALCOM II and PROMotion, and DGICyT PB 89/0379.

§ Universitat Pompeu Fabra, c/ Balmes 132, Barcelona 08008, Spain


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.