direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content


Prof. Dr. Peter Bürgisser


Technische Universität Berlin
Institut für Mathematik
Sekretariat MA 3-2
Straße des 17. Juni 136
10623 Berlin

Raum MA 317 (3. OG)
Institut für Mathematik


Beate Nießen
Raum MA 318
Tel.: +49 (0)30 314 - 25771


+49 (0)30 314 - 75902
+49 (0)30 314 - 25839

Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.


Exotic quantifiers, complexity classes, and complete problems
Citation key BC-Exotic-Quantifiers-Complexity-Classes-And-Complete-Problems-1
Author Peter Bürgisser and Felipe Cucker
Title of Book Proc. of ICALP 2007
Pages 207-218
Year 2007
Number 4596
Series Lecture Notes in Computer Science
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 usual quantifiers only.
Link to publication Link to original publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.