Exotic Quantifiers, Complexity Classes, and Complete Problems

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

12 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)135-170
Journal / PublicationFoundations of Computational Mathematics
Volume9
Issue number2
Online published25 Sep 2007
Publication statusPublished - Apr 2009

Abstract

We define new complexity classes in the Blum-Shub-Smale theory of computation over the reals, in the spirit of the polynomial hierarchy, with the help of infinitesimal and generic quantifiers. Basic topological properties of semialgebraic sets like boundedness, closedness, compactness, as well as the continuity of semialgebraic functions are shown to be complete in these new classes. All attempts to classify the complexity of these problems in terms of the previously studied complexity classes have failed. We also obtain completeness results in the Turing model for the corresponding discrete problems. In this setting, it turns out that infinitesimal and generic quantifiers can be eliminated, so that the relevant complexity classes can be described in terms of the usual quantifiers only.

Research Area(s)

  • BSS computation, Complete problems, Complexity classes, Genericity, Infinitesimals