Leitung

Prof. Dr. Peter Bürgisser

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

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

eMail
pbuerg@math.tu-berlin.de
contact form

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.

Counting Complexity Classes for Numeric Computations I: Semilinear Sets
Zitatschlüssel	BC-Counting-Complexity-Classes-For-Numeric-Computations-I-Semilinear-Sets
Autor	Peter Bürgisser and Felipe Cucker
Seiten	227-260
Jahr	2003
Journal	SIAM J. Comp.
Jahrgang	33
Nummer	1
Zusammenfassung	We define a counting class $\#P_textadd$ in the BSS-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 to compute basic topological invariants of semi-linear sets given by additive circuits. It turns out that the computation of the Euler characteristic is $FP_textadd^#P_textadd$-complete, while for fixed $k$, the computation of the $k$-th Betti number is $FPAR_textadd$-complete. Thus the latter is more difficult under standard complexity theoretic assumptions. We use all the above to prove some completeness results in the classical setting.

Schnellnavigation zur Seite über Nummerneingabe

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.