direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Book Chapters

Variations by complexity theorists on three themes of Euler, Bézout, Betti, and Poincaré
Citation key BC-2005-Variations-by-complexity-theorists-on-three-themes-of-Euler-Bezout-Betti-and-Poincare
Author Peter Bürgisser and Felipe Cucker
Title of Book Complexity of computations and proofs
Pages 73-152
Year 2005
Volume 13
Editor Jan Krajicek
Publisher Quaderni di Matematica
Abstract 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 to publication [1] Link to original publication [2] Download Bibtex entry [3]
------ Links: ------

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

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