TU Berlin

Fachgebiet Algorithmische AlgebraProf. Dr. Peter Bürgisser

Inhalt des Dokuments

zur Navigation

Leitung

Prof. Dr. Peter Bürgisser

Lupe

Anschrift
Technische Universität Berlin
Institut für Mathematik
Sekretariat MA 3-2
Straße des 17. Juni 136
10623 Berlin

Büro
Raum MA 317 (3. OG)
Institut für Mathematik

Kontakt

Sekretariat
Beate Nießen
Raum MA 318
Tel.: +49 (0)30 314 - 25771

eMail
peter.buergisser@offmath.tu-berlin.de

Telefon
+49 (0)30 314 - 75902
Faxgerät
+49 (0)30 314 - 25839

Sprechstunde
Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.

Publikationen

Counting Complexity Classes over the Reals I: The Additive Case
Zitatschlüssel BC-Counting-Complexity-Classes-Over-The-Reals-I-The-Additive-Case
Autor Peter Bürgisser and Felipe Cucker
Buchtitel In Proceedings of ISAAC 2003
Seiten 625-634
Jahr 2003
Nummer 2906
Verlag Springer
Serie Lecture Notes in Computer Science
Zusammenfassung We define a counting class $\#P_add$ in the Blum-Shub-Smale-setting of additive computations over the reals. Structural properties of this class are studied, including a characterization in terms of the classical counting class $\#P$ introduced by Valiant. We also establish transfer theorems for both directions between the real additive and the discrete setting. Then we characterize in terms of completeness results the complexity of computing basic topological invariants of semi-linear sets given by additive circuits. It turns out that the computation of the Euler characteristic is $FP^#P_add_add$-complete, while for fixed $k$, the computation of the $k$-th Betti number is $FPAR_add$-complete. Thus the latter is more difficult under standard complexity theoretic assumptions. We use all the above to prove some analogous completeness results in the classical setting.
Link zur Publikation Link zur Originalpublikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe