TU Berlin

Fachgebiet Algorithmische AlgebraPublications

Page Content

to Navigation

There is no English translation for this web page.

Search for Publication

Search for publications

All Publications

Counting Complexity Classes over the Reals I: The Additive Case
Citation key BC-Counting-Complexity-Classes-Over-The-Reals-I-The-Additive-Case
Author Peter Bürgisser and Felipe Cucker
Title of Book In Proceedings of ISAAC 2003
Pages 625-634
Year 2003
Number 2906
Publisher Springer
Series Lecture Notes in Computer Science
Abstract 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 to publication Link to original publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe