direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Search for Publication

Search for publications




All Publications

Counting Complexity Classes for Numeric Computations I: Semilinear Sets
Citation key BC-Counting-Complexity-Classes-For-Numeric-Computations-I-Semilinear-Sets
Author Peter Bürgisser and Felipe Cucker
Pages 227-260
Year 2003
Journal SIAM J. Comp.
Volume 33
Number 1
Abstract 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.
Link to publication Link to original publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

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