Inhalt des Dokuments
Book Chapters
| 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. |
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe
Hilfsfunktionen
- Schriftgröße:
Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.