Inhalt des Dokuments
Prof. Dr. Peter Bürgisser
- © Peter Bürgisser
Technische Universität Berlin
Institut für Mathematik
Sekretariat MA 3-2
Straße des 17. Juni 136
10623 Berlin
Büro
Raum MA 317 (3. OG)
Institut für Mathematik
Sprechstunde
Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.
Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.
Publikationen
| Zitatschlüssel | BC-Exotic-Quantifiers-Complexity-Classes-And-Complete-Problems-1 |
|---|---|
| Autor | Peter Bürgisser and Felipe Cucker |
| Buchtitel | Proc. of ICALP 2007 |
| Seiten | 207-218 |
| Jahr | 2007 |
| Nummer | 4596 |
| Serie | Lecture Notes in Computer Science |
| Zusammenfassung | 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. |
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe