Inhalt des Dokuments
Book Chapters
| Zitatschlüssel | B-2003-Lower-Bounds-and-Real-Algebraic-Geometry |
|---|---|
| Autor | Peter Bürgisser |
| Buchtitel | Algorithmic and Quantitative Real Algebraic Geometry |
| Seiten | 35-54 |
| Jahr | 2003 |
| Jahrgang | 60 |
| Notiz | Erratum: http://www.math.tu-berlin.de/algebra/work/erratum.pdf |
| Herausgeber | Saugata Basu and Laureano Gonzalez-Vega |
| Verlag | AMS |
| Serie | DIMACS |
| Zusammenfassung | Many relevant problems in symbolic computation and computational geometry can be formalized as semi-algebraic computation or decision problems, to be solved by means of algebraic computation trees. It is a general paradigm that a complicated geometrical, topological, or combinatorial structure of a problem should result in high computational complexity. This survey outlines some of the ideas leading to lower bounds in terms of degree, Betti numbers, and number of faces of an arrangement or a polyhedron, emphasizing the role of real algebraic geometry in this endeavour. The impact of randomization on decision complexity is briefly discussed. |
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.