Exotic Quantifiers, Complexity Classes, and Complete Problems

Peter Bürgisser; Felipe Cucker

doi:10.1007/978-3-540-73420-8_20

Exotic Quantifiers, Complexity Classes, and Complete Problems

Peter Bürgisser
, Felipe Cucker

Department of Mathematics

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

2 Citations (Scopus)

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.

Original language	English
Title of host publication	Automata, Languages and Programming
Subtitle of host publication	34th International Colloquium, ICALP 2007 - Proceedings
Editors	Lars Arge, Christian Cachin, Tomasz Jurdzinski, Andrzej Tarlecki
Publisher	Springer Verlag
Pages	207-218
ISBN (Print)	3540734198, 9783540734192
DOIs	https://doi.org/10.1007/978-3-540-73420-8_20
Publication status	Published - Jul 2007
Event	34th International Colloquium on Automata, Languages and Programming (ICALP 2007) - Wroclaw, Poland Duration: 9 Jul 2007 → 13 Jul 2007

Publication series

Name	Lecture Notes in Computer Science
Volume	4596
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	34th International Colloquium on Automata, Languages and Programming (ICALP 2007)
Place	Poland
City	Wroclaw
Period	9/07/07 → 13/07/07

Access Output

10.1007/978-3-540-73420-8_20

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Bürgisser, P., & Cucker, F. (2007). Exotic Quantifiers, Complexity Classes, and Complete Problems. In L. Arge, C. Cachin, T. Jurdzinski, & A. Tarlecki (Eds.), Automata, Languages and Programming: 34th International Colloquium, ICALP 2007 - Proceedings (pp. 207-218). (Lecture Notes in Computer Science; Vol. 4596). Springer Verlag. https://doi.org/10.1007/978-3-540-73420-8_20

@inproceedings{737812b7832c4e76a1b76753b509014d,

title = "Exotic Quantifiers, Complexity Classes, and Complete Problems",

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.",

author = "Peter B{\"u}rgisser and Felipe Cucker",

year = "2007",

month = jul,

doi = "10.1007/978-3-540-73420-8\_20",

language = "English",

isbn = "3540734198",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "207--218",

editor = "Lars Arge and Christian Cachin and Tomasz Jurdzinski and Andrzej Tarlecki",

booktitle = "Automata, Languages and Programming",

address = "Germany",

note = "34th International Colloquium on Automata, Languages and Programming (ICALP 2007) ; Conference date: 09-07-2007 Through 13-07-2007",

}

Bürgisser, P & Cucker, F 2007, Exotic Quantifiers, Complexity Classes, and Complete Problems. in L Arge, C Cachin, T Jurdzinski & A Tarlecki (eds), Automata, Languages and Programming: 34th International Colloquium, ICALP 2007 - Proceedings. Lecture Notes in Computer Science, vol. 4596, Springer Verlag, pp. 207-218, 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), Wroclaw, Poland, 9/07/07. https://doi.org/10.1007/978-3-540-73420-8_20

Exotic Quantifiers, Complexity Classes, and Complete Problems. / Bürgisser, Peter; Cucker, Felipe.
Automata, Languages and Programming: 34th International Colloquium, ICALP 2007 - Proceedings. ed. / Lars Arge; Christian Cachin; Tomasz Jurdzinski; Andrzej Tarlecki. Springer Verlag, 2007. p. 207-218 (Lecture Notes in Computer Science; Vol. 4596).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Exotic Quantifiers, Complexity Classes, and Complete Problems

AU - Bürgisser, Peter

AU - Cucker, Felipe

PY - 2007/7

Y1 - 2007/7

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/38149140182

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-38149140182&origin=recordpage

U2 - 10.1007/978-3-540-73420-8_20

DO - 10.1007/978-3-540-73420-8_20

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 3540734198

SN - 9783540734192

T3 - Lecture Notes in Computer Science

SP - 207

EP - 218

BT - Automata, Languages and Programming

A2 - Arge, Lars

A2 - Cachin, Christian

A2 - Jurdzinski, Tomasz

A2 - Tarlecki, Andrzej

PB - Springer Verlag

T2 - 34th International Colloquium on Automata, Languages and Programming (ICALP 2007)

Y2 - 9 July 2007 through 13 July 2007

ER -

Exotic Quantifiers, Complexity Classes, and Complete Problems

Abstract

Publication series

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this