TU Berlin

Fachgebiet Algorithmische AlgebraBook Chapters

Inhalt des Dokuments

zur Navigation

Book Chapters

Variations by complexity theorists on three themes of Euler, Bézout, Betti, and Poincaré
Zitatschlüssel BC-2005-Variations-by-complexity-theorists-on-three-themes-of-Euler-Bezout-Betti-and-Poincare
Autor Peter Bürgisser and Felipe Cucker
Buchtitel Complexity of computations and proofs
Seiten 73-152
Jahr 2005
Jahrgang 13
Herausgeber Jan Krajicek
Verlag Quaderni di Matematica
Zusammenfassung This paper surveys some connections between geometry and complexity. A main role is played by some quantities - degree, Euler characteristic, Betti numbers - associated to algebraic or semialgebraic sets. This role is twofold. On the one hand, lower bounds on the deterministic time (sequential and parallel) necessary to decide a set S are established as functions of these quantities associated to S. The optimality of some algorithms is obtained as a consequence. On the other hand, the computation of these quantities gives rise to problems which turn out to be hard (or complete) in different complexity classes. These two kind of results thus turn the quantities above into measures of complexity in two quite different ways.
Link zur Publikation Link zur Originalpublikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe